The subset sum problem refers to two problems.
The first ("given sum problem") is the problem of finding what subset of a list of integers has a given sum, which is an integer relation problem where the relation coefficients 
are 0 or 1.
The ("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) using the tools of algebraic geometry, with the answer given for 
numbers by the first 
positive integers: 
. Proctor (1982) gave the first 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 given sum problem is an NP-complete problem. For small cases, it can be solved using generating
functions. Consider the number of ways 
to select 
out of 
given 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)
|
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) |
A nice explicit example original 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)
|
(Borwein and Bailey 2003, p. 21).
