Describe sum of subset problem.
Subject Algorithm Design Set: 5.(b) Marks: 5 Year: 2010

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)