Subset Sum Problem

Subset Sum asks a yes/no question that looks simple but hides exponential blow-up: out of all possible subsets, does any one of them add up to a given target? The trick is to stop enumerating subsets and instead fill a small boolean table that remembers which sums are reachable.

The slow way first

The brute-force idea is to try every subset. With n items there are 2^n subsets, so checking them all is O(2ⁿ) — for 30 items that is already a billion combinations. We need to avoid re-deriving the same partial sums over and over.

The question to ask: while I decide about one item, what do I wish I already knew? I wish I knew, for every sum s, whether the earlier items could already make s. If I knew that, deciding about the next item is just a quick lookup. That is exactly what a DP table stores.

The idea: a table of reachable sums

Define dp[i][s] = "can some subset of the first i items add up to exactly s?" For each cell there are two choices for item i:

• Skip it — then the answer is whatever the row above says: dp[i - 1][s].
• Take it — only possible if s >= a[i - 1]; then we need the rest to make s - a[i - 1], i.e. dp[i - 1][s - a[i - 1]].

So dp[i][s] = dp[i - 1][s] OR dp[i - 1][s - a[i - 1]]. Each cell looks straight up (skip) or up-and-left by the item's value (take).

The base case seeds everything: dp[i][0] is always True (the empty subset makes sum 0), and dp[0][s] for s > 0 is False (no items, no positive sum).

Walk through it

Step through the animation. We fill the grid row by row for a = [3, 34, 4, 12] and target = 7. Watch the highlighted cells in the row above feed each new cell. Rows for 34 and 12 just copy down (both exceed the target, so they never fit). The magic happens in the +4 row: dp[3][7] reads dp[2][3] (the subset {3}) and lights up — proving {3, 4} reaches 7.

Pseudocode

make a table dp[0..n][0..target] of False
for every row i:
    dp[i][0] = True                 # empty subset makes 0
for i from 1 to n:
    for s from 1 to target:
        dp[i][s] = dp[i-1][s]       # skip item i
        if s >= a[i-1] and dp[i-1][s - a[i-1]]:
            dp[i][s] = True          # take item i
return dp[n][target]

The Python solution

def subset_sum(a, target):
    n = len(a)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True
    for i in range(1, n + 1):
        for s in range(1, target + 1):
            dp[i][s] = dp[i - 1][s]
            if s >= a[i - 1]:
                if dp[i - 1][s - a[i - 1]]:
                    dp[i][s] = True
    return dp[n][target]

• dp is an (n + 1) x (target + 1) grid of booleans, all starting False.
• The first loop sets dp[i][0] = True for every row — the empty subset always reaches sum 0.
• For each item i and sum s, line 8 first copies the skip case from the row above.
• Line 9 guards the take case: we can only use the item if it fits (s >= a[i - 1]).
• If the leftover sum s - a[i - 1] was reachable without this item, taking it reaches s, so the cell becomes True.
• The answer is the bottom-right corner, dp[n][target].

Complexity

This is pseudo-polynomial: fast when target is modest, but it scales with the numeric value of the target, not just the count of items. The space can be squeezed to O(target) by keeping only one row and iterating s downward — the classic rolling-array trick.

When this pattern shows up

Practice