Subset Sum Problem - Pseudo-polynomial Time Dynamic Programming Solution

Pseudo-polynomial Time Dynamic Programming Solution

The problem can be solved as follows using dynamic programming. Suppose the sequence is

x₁, ..., x_n

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 x₁, ..., 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₁ == 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 − x_i) = 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(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 x_i is positive and bounded by a fixed constant r, Pisinger found a linear time algorithm having time complexity O(nr).