# Subset sum problem

• Mar 23rd 2011, 10:54 PM
jamix
Subset sum problem
Subset sum problem - Wikipedia, the free encyclopedia

I thought this problem was solvable in polynomial time using generating functions?

There is a algorithm given in the wiki link above that uses recursive functions. It says the following:
Quote:

The problem can be solved as follows using dynamic programming. Suppose the sequence is
x1, ..., xn and we wish to determine if there is a nonempty subset which sums to 0. Let N be the sum of the negative values and P the sum of the positive values. Define the boolean-valued function Q(i,s) to be the value (true or false) of
"there is a nonempty subset of x1, ..., xi which sums to s". Thus, the solution to the problem is the value of Q(n,0).
Clearly, Q(i,s) = false if s < N or s > P so these values do not need to be stored or computed. Create an array to hold the values Q(i,s) for 1 ≤ in and NsP.
The array can now be filled in using a simple recursion. Initially, for NsP, set
Q(1,s) := (x1 == s). Then, for i = 2, …, n, set
Q(i,s) := Q(i − 1,s) or (xi = s) or Q(i − 1,sxi) for NsP. For each assignment, the values of Q on the right side are already known, either because they were stored in the table for the previous value of i or because Q(i − 1,sxi) = false if sxi < N or sxi > P. Therefore, the total number of arithmetic operations is O(n(PN)). For example, if all the values are O(nk) for some k, then the time required is O(nk+2).
This algorithm is easily modified to return the subset with sum 0 if there is one.
This solution does not count as polynomial time in complexity theory because PN is not polynomial in the size of the problem, which is the number of bits used to represent it. This algorithm is polynomial in the values of N and P, which are exponential in their numbers of bits.
So if say one of our \$\displaystyle x_i\$ is extraordinarily large, then that would make this algorithm inefficient because then P or N would be huge too.