The idea: can some of these numbers make exactly T?

Subset sum asks a yes/no question: given whole numbers w1 … wn and a target T, is there a subset that adds up to exactly T? For {3, 34, 4, 12, 5, 2} and T = 9 the answer is yes (4 + 5); for T = 30 it is no. Trying all 2n subsets works but blows up fast. Dynamic programming instead answers a smaller question for every pair (first i items, sum s) and keeps the answers in a table of true and false.

Cell dp[i][s] in a table of true and false reads two cells in the row above: dp[i-1][s] straight above (skip item i) and dp[i-1][s - w_i], w_i columns to the left (take item i). The cell is true if either one is true. Example: dp[3][7] with w3 = 4: skip gives dp[2][7] = F, take gives dp[2][3] = T, so dp[3][7] = T.
Each cell is true when the cell above is true (skip the item) or the cell wi to the left of it is true (take the item).

The recurrence: skip or take

Let dp[i][s] be true when some subset of the first i items adds up to exactly s. Look at item i. Either the subset leaves it out, and then the first i − 1 items must already make s; or it uses it, and then the first i − 1 items must make the rest, s − wi:

dp[0][0] = true                       (the empty set sums to 0)
dp[0][s] = false          for s > 0
dp[i][s] = dp[i-1][s]                            skip item i
           OR (w_i <= s AND dp[i-1][s - w_i])    take item i

It is the 0/1 knapsack table with booleans instead of values: "max" becomes "or", and there is no value to add.

Filling the table

Row 0 is true only at s = 0. After that the page fills row by row, left to right. In the animation the cell being filled has a red ring, the skip source straight above is blue and the take source wi columns to the left is orange. The current cell panel shows the "or". True cells are green, false cells red. (Demo: target 9)

A whole row is easy to read at once: row i is row i − 1, plus a copy of it shifted right by wi. An item bigger than the target, like 34, never fits, so its row is a plain copy. Choose one row per step in Options to fill a row at a time; the ringed cells are the newly reachable sums. (Demo: target 30)

The answer is the bottom-right cell, dp[n][T].

Trace back: which items?

The table says yes or no, not which items. To find a subset, start at dp[n][T] and go up one row per item. If dp[i-1][s] is true, the earlier items can make s without item i, so skip it and move straight up. Otherwise item i must have been taken: record it and move to dp[i-1][s - wi]. The walk always ends at dp[0][0]. Path cells turn yellow and each taken item flies to the result panel. (Demo: target 26 takes five items: 3 + 4 + 12 + 5 + 2.)

For target 9 the walk skips 2 (dp[5][9] is already true), takes 5, skips 12, takes 4 and skips 34 and 3, so the subset is {4, 5}. Preferring "skip" is a choice; {3, 4, 2} also works and a "take first" rule would find it.

Worked example

The full table for {3, 34, 4, 12, 5, 2} and T = 9 (T = true, . = false):

        s =  0  1  2  3  4  5  6  7  8  9
none         T  .  .  .  .  .  .  .  .  .
w1 = 3       T  .  .  T  .  .  .  .  .  .
w2 = 34      T  .  .  T  .  .  .  .  .  .
w3 = 4       T  .  .  T  T  .  .  T  .  .
w4 = 12      T  .  .  T  T  .  .  T  .  .
w5 = 5       T  .  .  T  T  T  .  T  T  T
w6 = 2       T  .  T  T  T  T  T  T  T  T

Row 3 adds 4 to the sums {0, 3} of row 2, giving {0, 3, 4, 7}. Row 5 adds 5 and reaches 9 for the first time (4 + 5). With T = 30 the last row stays false at 30: without 34 the items add up to only 26.

Equal partition: subset sum with T = total / 2

The partition problem asks whether the items can be split into two groups with equal sums. If one group sums to half the total, the rest automatically sums to the other half, so it is subset sum with T = total / 2. {1, 5, 11, 5} has total 22, so the target is 11; the trace back takes 11 and the other half is 1 + 5 + 5. (Demo: partition {1, 5, 11, 5})

If the total is odd, no split can work: each half would need a fraction. The page answers No without drawing a table. (Demo: partition {2, 3, 4})

The items 1, 5, 11, 5 have total 22. Subset sum with target 22 / 2 = 11 finds the subset {11}; the remaining items 1 + 5 + 5 also sum to 11, so the two halves are equal. Below, {2, 3, 4} has total 9, which is odd, so the answer is no at once.
Finding one half that sums to total / 2 is enough: the leftover items are the other half.

Running time: pseudo-polynomial

The table has (n + 1)(T + 1) cells, each done in constant time, so the algorithm takes Θ(nT) time. That is fast when T is small, but T is a number, not a count: writing it down takes only about log T digits, so the running time is exponential in the input size. This is called pseudo-polynomial, and it fits with subset sum being NP-complete.

For the yes/no answer one row is enough: keep a single array and loop s from T down to wi, setting dp[s] = dp[s] or dp[s - w_i]. Looping upwards would let an item be used twice. The trace back needs the full table.

problemcell holdscombine
subset sum (this page)true / falseskip OR take
0/1 knapsackbest valuemax(skip, value + take)
counting subsetsnumber of subsetsskip + take
coin change (ways)number of wayscoins may repeat

See also 0/1 Knapsack, the same table with values and a max, and Coin Change, which counts ways when each coin may be used many times. Backtracking over subsets is the brute-force alternative.

When the state must remember which items were used rather than a running total, see Bitmask DP over Subsets.

What the page leaves out

At most 8 items and targets up to 30, so the table fits on the screen. The page leaves out negative numbers (the sums then need an offset), listing every subset that works instead of one, counting them, the bitset trick that fills a row with one shift-and-or, meet-in-the-middle for few items with huge values, and splitting into k > 2 equal groups.