There are two problems commonly known as the subset sum problem.
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).
Similarly, the numbers of different subset sums for 
, 2, ... are 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, ... (OEIS
A000124). For example, for 
, the subsets of 
are
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
so the sum appearing most often is 3, which occurs twice, and the number of different sums is 7.
The given sum problem is NP-complete. For small cases, it 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
 |
(9)
|
Upon expanding in powers of 
, this becomes
 |
(10)
|
But as a result of the exponent law 
, 
is precisely the desired generating
function
 |
(11)
|
For example, consider the problem of picking 
objects from the set 
. The generating function 
is
 |
(12)
|
So, for example, selecting 
objects has the generating function
 |  |  |
(13)
|
 |  |  |
(14)
|
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
 |
(15)
|
(Borwein and Bailey 2003, p. 21).
