# Subset sum problem

The subset sum problem asks, given a set of n positive integers and a target integer t, whether some subset of the integers sums exactly to t. It was one of the original 21 problems proved NP-complete in Richard Karp's 1972 paper and has been studied intensively for at least five decades.<sup>[1](https://arxiv.org/pdf/2301.07134)</sup> Despite this worst-case hardness, the problem admits unusually fast algorithms in several parameter regimes, and its presumed difficulty was once the foundation of a public-key cryptosystem.<sup>[2](https://dro.deakin.edu.au/articles/chapter/The_0-1_Knapsack_polytope_a_starting_point_for_cryptanalysis_of_Knapsack_ciphers_/20918149)</sup>

| Key fact | Detail |
|---|---|
| Definition | Given n positive integers and a target t, decide whether a subset sums to t; equivalently, compute all y in {0, …, t} reachable as a subset sum<sup>[3](https://arxiv.org/abs/2601.01390)</sup> |
| Complexity | NP-complete, one of Karp's original 21 problems (1972)<sup>[1](https://arxiv.org/pdf/2301.07134)</sup> |
| Dynamic programming | Bellman's 1957 algorithm runs in O(nt) time using Ω(t) space; pseudopolynomial, not polynomial in the input length (n + 1) log t<sup>[4](https://epubs.siam.org/doi/10.1137/1.9781611976465.106)</sup><sup> • </sup><sup>[5](https://www.cs.cornell.edu/courses/cs4820/2018fa/lectures/subset_sum.pdf)</sup> |
| Worst-case exponential | Meet-in-the-middle (Horowitz and Sahni, 1974) runs in O(2<sup>n/2</sup>) time; no worst-case improvement on the 2<sup>n/2</sup> exponent existed for almost fifty years<sup>[1](https://arxiv.org/pdf/2301.07134)</sup> |
| Pseudopolynomial state of the art | Deterministic Õ(t√n) (Koiliaris and Xu, SODA 2017); randomized Õ(n + t) (Bringmann, SODA 2017); first deterministic Õ(t) by Chan (2026)<sup>[3](https://arxiv.org/abs/2601.01390)</sup> |
| Cryptographic history | The Merkle–Hellman knapsack cryptosystem (1978) rested on subset sum and was broken by Adi Shamir<sup>[2](https://dro.deakin.edu.au/articles/chapter/The_0-1_Knapsack_polytope_a_starting_point_for_cryptanalysis_of_Knapsack_ciphers_/20918149)</sup> |

## The problem and its complexity

An instance consists of a list X = (x₁, …, xₙ) of positive integers and a target t; the answer is a subset S with Σ<sub>i∈S</sub> xᵢ = t, or a report that none exists.<sup>[1](https://arxiv.org/pdf/2301.07134)</sup> A proposed subset can be verified by adding at most n numbers, so the problem is in NP, and a reduction from SAT establishes [NP-completeness](https://www.edgepedia.org/np-completeness).<sup>[5](https://www.cs.cornell.edu/courses/cs4820/2018fa/lectures/subset_sum.pdf)</sup>

Subset Sum is a special case of the 0-1 knapsack problem, obtained by setting each item's value equal to its weight.<sup>[5](https://www.cs.cornell.edu/courses/cs4820/2018fa/lectures/subset_sum.pdf)</sup> It is **weakly NP-complete**: the standard O(nW) dynamic program runs in time polynomial in the numeric value of the target, but an integer W needs only log W digits to write down, so O(nW) is not polynomial in the input length (n + 1) log W.<sup>[5](https://www.cs.cornell.edu/courses/cs4820/2018fa/lectures/subset_sum.pdf)</sup>

## Dynamic programming

Bellman's 1957 dynamic programming algorithm computes the set of all subset sums up to t in O(nt) time, requiring Ω(t) space.<sup>[4](https://epubs.siam.org/doi/10.1137/1.9781611976465.106)</sup> Written as a generating function, the problem is multiplication of polynomials, and Ce Jin and Hongxun Wu exploited this with FFT techniques to give a simple randomized Õ(n + t) algorithm that actually solves the counting version modulo a prime p > t.<sup>[6](https://arxiv.org/abs/1807.11597)</sup>

A long line of work has attacked the O(nt) bound. At SODA 2017, Koiliaris and Xu gave a deterministic algorithm running in Õ(t√n) time, and Karl Bringmann gave a randomized Õ(n + t) algorithm using two-stage color-coding, a bound believed to be near-optimal.<sup>[3](https://arxiv.org/abs/2601.01390)</sup><sup> • </sup><sup>[6](https://arxiv.org/abs/1807.11597)</sup> In 2026, Timothy M. Chan presented the first deterministic algorithm running in Õ(t) time, removing the randomness from Bringmann's bound; the same technique derandomizes output-sensitive algorithms of Bringmann and Nakos running in Õ(|out|<sup>4/3</sup>) and Õ(|out|√n) time, and a fine-grained reduction from 0-1 knapsack to min-plus convolution by Cygan et al.<sup>[3](https://arxiv.org/abs/2601.01390)</sup>

**Output-sensitive and structure-sensitive bounds.** Bellman's algorithm runs in O(|𝒮(X, t)| · n) time, where 𝒮(X, t) is the set of distinct subset sums up to t. Later algorithms beat it only in specific parameter regimes, and it remained open whether Õ(|𝒮(X, t)| · n<sup>1−ε</sup>) time was achievable; a 2024 algorithm resolved this with Õ(|𝒮(X, t)| · √n) time, improving on Bellman in all regimes by a factor of nearly √n.<sup>[7](https://arxiv.org/abs/2410.21942)</sup> For dense inputs, Galil and Margalit gave an algorithm running in O(ℓ log ℓ) time, where ℓ bounds the element size, and O(m) time for dense enough inputs with targets near the middle sum.<sup>[8](https://epubs.siam.org/doi/10.1137/0220072)</sup>

## Space and low-space algorithms

Bellman's algorithm's Ω(t) space can be a bigger obstacle than its time. Jin, Vyas, and Williams demonstrated that Subset Sum admits an Õ(nt)-time, O(log(nt))-space algorithm using O(log n log log n + log t) random bits, a marked advance over Bringmann's Õ(nt<sup>1+ε</sup>)-time, Õ(n log t)-space method; additionally, they established a trade-off between time and space: Õ((n + t) · k) time together with O((t/k) polylog(nt)) space, for any 1 ≤ k ≤ min{n, t}.<sup>[4](https://epubs.siam.org/doi/10.1137/1.9781611976465.106)</sup>

## Exponential-time algorithms

Exhaustive search over all subsets takes 2<sup>n</sup> · poly(n) time. In 1974, Ellis Horowitz and Sartaj Sahni introduced the meet-in-the-middle technique, splitting the input into two halves and matching sums from each side, giving an O(2<sup>n/2</sup>)-time algorithm in standard RAM models.<sup>[1](https://arxiv.org/pdf/2301.07134)</sup> The same idea, published three years later by [Whitfield Diffie](https://www.edgepedia.org/whitfield-diffie) and Martin Hellman, became a cryptanalytic tool against Double DES.<sup>[9](https://unseel.com/cs/meet-in-the-middle)</sup>

Since 1974, obtaining a 2<sup>(1/2−c)n</sup>-time worst-case algorithm for some constant c > 0 has been a stated major goal of the exact exponential algorithms community.<sup>[1](https://arxiv.org/pdf/2301.07134)</sup> Progress came on other axes first:

- Schroeppel and Shamir (1981) kept the 2<sup>n/2</sup> · poly(n) time but cut space to 2<sup>n/4</sup> · poly(n).<sup>[1](https://arxiv.org/pdf/2301.07134)</sup>
- Nederlof and Węgrzycki further improved the space to 2<sup>0.249999n</sup>.<sup>[1](https://arxiv.org/pdf/2301.07134)</sup>
- On average-case instances, Howgrave-Graham and Joux gave 2<sup>0.337n</sup> time, improved to 2<sup>0.291n</sup> by Becker, Coron, and Joux.<sup>[1](https://arxiv.org/pdf/2301.07134)</sup>
- The related Equal Subset Sum problem, which seeks two subsets with the same sum, can be solved exponentially faster than meet-in-the-middle suggests.<sup>[1](https://arxiv.org/pdf/2301.07134)</sup>

A 2023 paper achieved the first nontrivial worst-case speedup of meet-in-the-middle itself, giving randomized algorithms running in O(2<sup>n/2</sup> · n<sup>−γ</sup>) for constants γ > 0, with the fastest at O(2<sup>n/2</sup> · n<sup>−0.5023</sup>); the authors describe such polynomial-factor savings as analogous to log-shaving improvements on polynomial-time algorithms.<sup>[1](https://arxiv.org/pdf/2301.07134)</sup> A 2025 certificate-sensitive algorithm enumerates the distinct subset sums in deterministic O(U · n²) time, where U = |Σ(S)|, with a randomized variant in expected O(U · n) time and a worst-case guarantee of O*(2<sup>n/2−ε</sup>) for some constant ε > 0.<sup>[10](https://arxiv.org/abs/2507.15511)</sup>

## Cryptography

The knapsack cryptosystem of [Ralph Merkle](https://www.edgepedia.org/ralph-merkle) and Martin Hellman (1978), one of the earliest public-key schemes, based its security on the difficulty of solving subset sum problems.<sup>[2](https://dro.deakin.edu.au/articles/chapter/The_0-1_Knapsack_polytope_a_starting_point_for_cryptanalysis_of_Knapsack_ciphers_/20918149)</sup> Knapsack-based systems were long viewed as attractive for their NP-completeness and fast encryption, but most were broken because the underlying knapsack instances had low density; a collision algorithm breaks a knapsack cryptosystem in O(2<sup>n/2</sup>) operations.<sup>[11](https://www.sciencedirect.com/science/article/abs/pii/S0020025507001545)</sup><sup> • </sup><sup>[12](https://ochicken.net/library/Cryptography/%28Undergraduate%20texts%20in%20mathematics%29%20Jeffrey%20Hoffstein%2C%20Jill%20Pipher%2C%20J.H.%20Silverman%20-%20An%20introduction%20to%20mathematical%20cryptography-Springer%20%282008%29.pdf)</sup> The original Merkle–Hellman system was broken by [Adi Shamir](https://www.edgepedia.org/adi-shamir), shown in his 1984 work, and later lattice reduction attacks finished the family; the scheme survives mainly as a teaching introduction to LLL reduction rather than as a cipher.<sup>[13](https://wiredspace.wits.ac.za/server/api/core/bitstreams/4572859a-8a49-4bda-9627-ef5ab3a99606/content)</sup><sup> • </sup><sup>[14](https://ctfpal.com/tools/knapsack-subset-sum)</sup> Later designs sought high knapsack density, above 1.06 in the worst case, to resist low-density subset-sum attacks.<sup>[11](https://www.sciencedirect.com/science/article/abs/pii/S0020025507001545)</sup> Modern lattice-based cryptography uses different constructions such as learning with errors, related to subset sum only through the underlying mathematics.<sup>[15](https://www.gopher.security/post-quantum/assessing-the-security-of-knapsack-public-key-cryptography)</sup>

## References

1. [Subset Sum in Time 2^{n/2}/poly(n), arXiv:2301.07134](https://arxiv.org/pdf/2301.07134)
2. [The 0-1 Knapsack polytope – a starting point for cryptanalysis of Knapsack ciphers?, Deakin University](https://dro.deakin.edu.au/articles/chapter/The_0-1_Knapsack_polytope_a_starting_point_for_cryptanalysis_of_Knapsack_ciphers_/20918149)
3. [Timothy M. Chan. Derandomizing Pseudopolynomial Algorithms for Subset Sum, arXiv:2601.01390](https://arxiv.org/abs/2601.01390)
4. [Ce Jin, Nikhil Vyas, Ryan Williams. Fast Low-Space Algorithms for Subset Sum, SODA 2021](https://epubs.siam.org/doi/10.1137/1.9781611976465.106)
5. [Subset Sum is NP-complete, CS 4820 lecture notes, Cornell University](https://www.cs.cornell.edu/courses/cs4820/2018fa/lectures/subset_sum.pdf)
6. [Ce Jin, Hongxun Wu. A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum, SOSA 2019](https://arxiv.org/abs/1807.11597)
7. [Beating Bellman's Algorithm for Subset Sum, arXiv:2410.21942](https://arxiv.org/abs/2410.21942)
8. [Zvi Galil, Oded Margalit. An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem, SIAM Journal on Computing](https://epubs.siam.org/doi/10.1137/0220072)
9. [Meet in the Middle — Complexity, Code & Explained, Unseel](https://unseel.com/cs/meet-in-the-middle)
10. [Jesus Salas. Certificate-Sensitive Subset Sum: Realizing Instance Complexity, arXiv:2507.15511](https://arxiv.org/abs/2507.15511)
11. [A knapsack-based probabilistic encryption scheme, Information Sciences 177(19), 2007](https://www.sciencedirect.com/science/article/abs/pii/S0020025507001545)
12. [Hoffstein, Pipher, Silverman. An Introduction to Mathematical Cryptography, Springer, section 6.2](https://ochicken.net/library/Cryptography/%28Undergraduate%20texts%20in%20mathematics%29%20Jeffrey%20Hoffstein%2C%20Jill%20Pipher%2C%20J.H.%20Silverman%20-%20An%20introduction%20to%20mathematical%20cryptography-Springer%20%282008%29.pdf)
13. [A Survey of the Mathematics of Cryptology, University of the Witwatersrand](https://wiredspace.wits.ac.za/server/api/core/bitstreams/4572859a-8a49-4bda-9627-ef5ab3a99606/content)
14. [Knapsack / subset-sum solver (Merkle-Hellman break), CTF Pal](https://ctfpal.com/tools/knapsack-subset-sum)
15. [Assessing the Security of Knapsack Public Key Cryptography, Gopher Security](https://www.gopher.security/post-quantum/assessing-the-security-of-knapsack-public-key-cryptography)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Combinatorics › Extremal and additive combinatorics › Sumsets and inverse additive problems*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license