Describe sum of subset problem.
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 a_i are 0 or 1.

The ("same sum problem") is the problem of finding a set of n 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 n numbers by the first n positive integers: {1,2,...,n}. Proctor (1982) gave the first elementary proof of this result. The maximal numbers of subsets of {1,2,...,n} having the same sum for n=1, 2, ... are 1, 1, 2, 2, 3, 5, 8, 14, 23, ... (OEIS A025591). Similarly, the numbers of different subset sums for n=1, 2, ... are 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, ... (OEIS A000124). For example, for n=3, the subsets of {1,2,3} are

sumemptyset = 0
(1)
1 = 1
(2)
2 = 2
(3)
3 = 3
(4)
1+2 = 3
(5)
1+3 = 4
(6)
2+3 = 5
(7)
1+2+3 = 6,
Login to post your comment.