subset-sum-wikipedia

Pseudo-polynomial time dynamic programming solution

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 zero. 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 ≤ 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) := (x1 == s).

Then, for i = 2, …, n, set

    Q(i,s) := Q(i − 1,s) or (xi == s) or Q(i − 1,s − xi)   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 − xi < N or s − xi > P. Therefore, the total number of arithmetic operations is O(n(P − N)). 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 P − N 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.

For the case that each xi is positive and bounded by a fixed constant r, Pisinger found a linear time algorithm having time complexity O(nr).[3]