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