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
 |
(1)
|
Upon expanding in powers of 
, this becomes
 |
(2)
|
But as a result of the exponent laws, in particular 
,
is precisely the desired generating function
 |
(3)
|
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
 |
(4)
|
So, for example, selecting 
objects has the generating
function
 |  |  |
(5)
|
 |  |  |
(6)
|
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.
 | solutions |
| 6 | (1, 2, 3) |
| 7 | (1, 2, 4) |
| 8 | (1, 2, 5), (1, 3, 4) |
| 9 | (1, 3, 5), (2, 3, 4) |
| 10 | (1, 4, 5), (2, 3, 5) |
| 11 | (2, 4, 5) |
| 12 | (3, 4, 5) |
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
 |
(7)
|
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 ![[-N,N]^d](/images/equations/SubsetSumProblem/Inline37.svg)
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.
