Download Wolfram Notebook

The subset sum problem refers to two problems.

The first ("given sum problem") asks for a subset of the positions in a list of integers whose values have a given sum. It is an integer relation problem with selection coefficients 0 or 1 after adjoining the negative of the target sum with its coefficient fixed at 1.

The second ("same sum problem") is the problem of finding a set of distinct positive real numbers with as large a collection as possible of subsets with the same sum (Proctor 1982).

The same sum problem was solved by Stanley (1980, pp. 178-179) using the tools of algebraic geometry, with the answer given for numbers by the first positive integers: . Proctor (1982, pp. 721-723) gave an elementary proof of this result. The maximal numbers of subsets of having the same sum for , 2, ... are 1, 1, 2, 2, 3, 5, 8, 14, 23, ... (OEIS A025591).

The decision version of the given sum problem asks whether such a subset exists and is an NP-complete problem for binary-encoded inputs. Finding a witness is the related NP-hard problem (Lagarias and Odlyzko 1985, p. 229). For small cases, the given sum problem can be solved using generating functions. Consider the number of ways to select out of given indexed integers , ..., such that their sum equals , and define the generating function

Upon expanding in powers of , this becomes

But as a result of the exponent laws, in particular , is precisely the desired generating function

Here is a Laurent polynomial, and is a polynomial when every .

For example, consider the problem of picking objects from the set . The generating function is

So, for example, selecting objects has the generating function

so the number of ways of picking three of the integers 1 through 5 and having them sum to , 11, ..., 6 are the coefficients of , namely 1, 1, 2, 2, 2, 1, and 1. These solutions are summarized in the following table.

An explicit example originally proposed by Pólya (1956) asks for the number of ways to make change from an American dollar (using pennies, nickels, dimes, quarters, and half-dollars). The answer of 292 is provided as the coefficient of the term in the series

for (Borwein and Bailey 2003, p. 21).

Chen et al. (2026) reported a deterministic algorithm for the vector version of the given sum problem. For fixed integer and , an explicitly listed multiset of vectors with integer coordinates in can be tested for a subset with a specified vector sum in word-RAM time, for . The bound is polynomial in the coordinate bound , not in its binary encoding length.

Chen et al. (2026) attribute the one-dimensional proof strategy to the authors and substantial proof development to GPT. They report that the deterministic multidimensional extension was obtained by GPT and supply a Lean formalization.

See also

Abundant Number, Grid Shading Problem, Integer Relation, Knapsack Problem, Lattice Reduction, Postage Stamp Problem, Pseudoperfect Number, Stöhr Sequence, Subset Sum, Weird Number

Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 22-24, 2003.Chen, L.; Mao, Y.; and Zhang, G. "Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time." 9 Oct 2026. https://arxiv.org/abs/2610.12953.Coster, M. J.; Joux, A.; LaMacchia, B. A.; Odlyzko, A. M.; Schnorr, C. P.; and Stern, J. "Improved Low-Density Subset Sum Algorithms." Comput. Complex. 2, 111-128, 1992.Coster, M. J.; LaMacchia, B. A.; Odlyzko, A. M.; and Schnorr, C. P. "An Improved Low-Density Subset Sum Algorithm." In Advances in Cryptology-EUROCRYPT '91 (Proc. Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK, April 8-11, 1991) (Ed. D. W. Davies). Berlin, Germany: Springer-Verlag, pp. 54-67, 1991. https://doi.org/10.1007/3-540-46416-6_4.Ferguson, H. R. P. and Bailey, D. H. "A Polynomial Time, Numerically Stable Integer Relation Algorithm." RNR Techn. Rept. RNR-91-032, Jul. 14, 1992.Lagarias, J. C. and Odlyzko, A. M. "Solving Low-Density Subset Sum Problems." J. ACM 32, 229-246, 1985.Pólya, G. "On Picture-Writing." Amer. Math. Monthly 63, 689-697, 1956.Proctor, R. A. "Solution of Two Difficult Combinatorial Problems with Linear Algebra." Amer. Math. Monthly 89, 721-734, 1982.Schnorr, C. P. and Euchner, M. "Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems." In Fundamentals of Computation Theory: Proceedings of the 8th International Conference, FCT '91 Gosen, Germany, September 9-13, 1991 (Ed. L. Budach). Berlin, Germany: Springer-Verlag, pp. 68-85, 1991. https://doi.org/10.1007/3-540-54458-5_51.Sloane, N. J. A. Sequence A025591 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. "Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property." SIAM J. Alg. Disc. Meth. 1, 168-184, 1980. https://doi.org/10.1137/0601021.

Referenced on Wolfram|Alpha

Subset Sum Problem

Cite this as:

Weisstein, Eric W. "Subset Sum Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SubsetSumProblem.html

Subject classifications