MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## #P version of SUBSET SUM

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

-
I don't know about the potential complexity, but often the practical complexity is that set of subset sums has fewer members than the set of subsets, so you might try computing the range of sums for a set, and then updating that range with each new element, including multiplicity. Worst case is exponential, but practical cases might yield nicely. Gerhard "Ask Me About System Design" Paseman, 2012.04.23 – Gerhard Paseman Apr 24 2012 at 5:34
By "size of the elements in $S$", do you mean their values or their number of bits? – Brendan McKay Apr 24 2012 at 13:16
By size of the element, I mean their absolute values. - Charles – Charles Bailey Apr 24 2012 at 19:05
In that case it is a standard exercise. Is this homework? – Brendan McKay Apr 25 2012 at 2:45

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

-
Can you comment on the number of solutions? That was the point of the posted question. Gerhard "Ask Me About System Design" Paseman, 2012.04.24 – Gerhard Paseman Apr 24 2012 at 21:56
Change the recurrence to $\#Q(i,s) = \#Q(i−1,s) + \#Q(i−1, s−x_i)$, with base cases $\#Q(0,0)=1$ and $\#Q(0,s)=0$ for all $s\ne 0$. – JeffE May 23 2012 at 7:51