Subset sum problem - Wikipedia, the free encyclopedia

I thought this problem was solvable in polynomial time using generating functions?

There is a algorithm given in the wiki link above that uses recursive functions. It says the following:
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 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 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.
So if say one of our x_i is extraordinarily large, then that would make this algorithm inefficient because then P or N would be huge too.