The problem can be solved as follows using

dynamic programming. Suppose the sequence is

*x*1, ...,

*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

*x*1, ...,

*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*) := (

*x*1 ==

*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*(

*n**k*+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.