How is the Subset Sum Problem NP-Complete?
The dynamic programming approaches only solve the problem in pseudopolynomial time.

Recall that the definition of (nondeterministic) polynomial time is that the problem must be solvable by a (nondeterministic) Turing machine whose running time is bounded by some polynomial in the size of the input.  The size of the input is the number of bits required to write it down.

Suppose we want to solve a subset sum instance where the set has size&nbsp;$k$ (i.e., contains $k$&nbsp;integers), and suppose this takes $n$&nbsp;bits to write down. The dynamic programming approach builds up a table with $k$&nbsp;rows and one column for each possible partial sum. How big is this table? Well, surely $k\leq n$, since we can't write down more than $n$&nbsp;numbers in only $n$&nbsp;bits.  However, a partial sum is the sum of some number of integers, each of which takes about $n/k$&nbsp;bits to write down. So that sum is also going to take roughly $n/k$&nbsp;bits to write down. That means that there are roughly $2^{n/k}$ columns in our table, so our table is exponentially large and we can't populate it in polynomial time.

The algorithm runs in pseudopolynomial time, which means that it runs in time bounded by some polynomial in the numbers represented in the instance, rather than in the number of bits required to write them down.

(In fact, this dynamic programming approach uses even more memory than doing dynamic programming on subsets.  Suppose, for example, that your set is $\{1,100\}$. There are only three nonempty subsets but you're likely to decide that a partial sum could be anywhere between $0$ and&nbsp;$101$, giving a table with two rows and $101$&nbsp;columns, instead of two rows and three columns.