The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, …, a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to zero. This problem is NP-complete.
The corresponding #P problem asks HOW MANY subsets of $S$ sum to zero.
Does anyone know of a pseudo-polynomial time algorithm for solving this enumeration version of the problem? It seems that it would have to be polynomial in the number of elements in S, the size of the elements in S, and the number of subsets that sum to zero. Beyond that, I don't know what the algorithm would look like. Perhaps a simple dynamic programming solution exists, but I'm not sure what it is.
Thanks,
Charles
Best Answer
The problem can be solved as follows using dynamic programming. Suppose the sequence is
x_1, ..., x_n and we wish to determine if there is a nonempty subset which sums to s. 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 x_1, ..., x_i 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 ≤ i ≤ n and N ≤ s ≤ P.
The array can now be filled in using a simple recursion. Initially, for N ≤ s ≤ P, set
Q(1,s) := (x_1 == s). Then, for i = 2, …, n, set
Q(i,s) := Q(i − 1,s) or (x_i == s) or Q(i − 1,s − x_i) for N ≤ s ≤ P. 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,s − xi) = false if s − x_i < N or s − x_i > P. Therefore, the total number of arithmetic operations is O(n(P − N)). For example, if all the values are O(n^k) for some k, then the time required is O(n)^k+2