# A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum

arXiv: https://arxiv.org/abs/1610.04712 · HTML: https://mlsanity.com/paper/1610.04712/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2016.

## Built on by (most cited first, 3 of 3)

- [Features for the 0-1 knapsack problem based on inclusionwise maximal solutions](https://mlsanity.com/paper/2211.09665/) (2022)
- [Projecting infinite time series graphs to finite marginal graphs using number theory](https://mlsanity.com/paper/2310.05526/) (2023)
- [The Subset Sum Matching Problem](https://mlsanity.com/paper/2508.19218/) (2025)

## Abstract (arXiv)

Given a set Z of n positive integers and a target value t, the Subset Sum problem asks whether any subset of Z sums to t. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves Subset Sum in time O(nt). This has been improved to O(n max Z) by Pisinger [J. Algorithms'99] and recently to tilde O(√n t) by Koiliaris and Xu [SODA'17]. Here we present a simple randomized algorithm running in time tilde O(n+t). This improves upon a classic algorithm and is likely to be near-optimal, since it matches conditional lower bounds from Set Cover and k-Clique. We then use our new algorithm and additional tricks to improve the best known polynomial space solution from time tilde O(n3 t) and space tilde O(n2) to time tilde O(nt) and space tilde O(n log t), assuming the Extended Riemann Hypothesis. Unconditionally, we obtain time tilde O(n t1+varepsilon) and space tilde O(n t^varepsilon) for any constant varepsilon > 0.