Subject  Algorithm Design 

NU Year  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)

