0/1 knapsack (subset sum)

35 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four stones weigh 1, 5, 11 and 5. Can you split them into two piles of equal weight? The total is 22, so each pile must weigh 11. By hand you look for stones adding to 11: 11 alone works, and so does 1 + 5 + 5. Yes.

In general the question is "is there a subset with sum exactly T?" Each stone is in or out, so there are 2ⁿ subsets: 16 here, but over a billion for 30 stones and far beyond that for 200. We need to stop thinking about subsets and start thinking about sums.

Build the structure, one piece at a time

Piece one: a row of yes/no boxes, dp[0] to dp[T], where dp[s] means "some stones considered so far add up to exactly s". Before any stone, only dp[0] is yes, because the empty pile weighs 0.

Piece two: the update for one stone of weight w. Every sum s that was reachable before gives a new reachable sum s + w:

dp[s] becomes yes if dp[s − w] was yes

Piece three, the one rule that makes it 0/1: sweep s from T down to w. Going downward, dp[s − w] is still the value from before this stone, so the stone is counted at most once. Sweeping upward would let the stone be reused: after making dp[5] yes with a 5-stone you would then read it to make dp[10] yes with the same stone.

After the second 5, dp[10] becomes yes from dp[5], which the first 5 created, so 5 + 5 = 10 is counted correctly, while dp[10] was not falsely set during the first 5's own sweep. dp[11] is yes, so the split exists.

Why it is correct

The invariant: after processing the first k stones, dp[s] is yes exactly when some subset of those k stones sums to s. Adding stone w, a subset of the first k + 1 stones either omits it (sums unchanged) or includes it (every old sum shifts by w). The downward sweep reads only old values, so it computes exactly the union of those two cases and nothing more.

Why it is fast

Each stone sweeps a row of T + 1 boxes:

work = n · T, memory = T + 1 booleans

For 200 stones and a target of 10,000 that is 2 million steps, against 2²⁰⁰ subsets. The catch is that the cost grows with the target value, not just the count, so it suits targets in the thousands, not the billions.

How to recognise it in an interview

Cues: "subset with sum", "partition into two equal halves", "each item used at most once", "assign + or − to reach a target", "minimise the difference between two piles". The first thing to say: "a boolean row over sums, one downward sweep per item." Partition Equal Subset Sum is the example above with T = total / 2. Target Sum asks for the number of ways to reach T; replace the booleans with counts and the same downward sweep adds dp[s − w] into dp[s].

02The idea in one line

For each item, sweep capacities downward so each item is used once.

Reach for it when: Partition equal subset sum, target sum, last stone weight II, ones and zeroes.

Cost: O(n · W) time.

03The walk-through, step by step

The video works one example: Partition Equal Subset Sum on [1,5,11,5]. These are its captions in order, so you can follow without the video or check a step you missed.

1. dp[0] is true; for each item, dp[c] |= dp[c − item] for c from high to low
2. Item 1: newly reachable sums 1
3. Item 5: newly reachable sums 6, 5
4. Downward sweep matters: dp[10] used dp[5] from before item 5, so 5 is not counted twice
5. Item 11: newly reachable sums 11
6. Item 5: newly reachable sums 10
7. dp[11] is true: {1, 5, 5} sums to 11, the array can be split
8. One row of size target per item: O(n · target)

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).