Knapsack DP¶
Also known as: 0/1 Knapsack, Unbounded Knapsack, Subset Sum
You're choosing items against a budget. For each item and each possible remaining budget, the answer is the better of "take it" and "skip it." Whether you may reuse an item — and therefore which direction you iterate the budget — is the only thing that separates the two famous variants.
Before you start¶
What 'solved properly' looks like
Target: O(n × capacity). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You build a table where rows are items (or coin types) and columns are capacities (from 0 up to the target). Each cell answers: "can I reach this exact capacity using the first i items?" For 0/1 knapsack (each item once), you iterate capacity downward so no item is reused. For unbounded knapsack (unlimited uses), you iterate upward so items can be reused. That loop direction is the entire difference between the two variants.
Why it matters: An enormous number of interview problems are knapsack in a costume: coins, targets, partitions, subsets summing to a value. Recognising the costume is the skill, and the loop-direction rule is the single most important thing to internalise.
When to reach for it¶
Reach for it when you pick items subject to a capacity or exact target: "can we make exactly this sum", "fewest coins to make N", "partition into two equal halves", or "each item usable once" (0/1) versus "unlimited times" (unbounded).
When not to use it
The loop direction over capacity is the classic silent bug — descending for 0/1 (each item used once), ascending for unbounded (items reusable). Get it backwards and you solve the wrong problem while your tests pass on small inputs. Also note this is pseudo-polynomial: the cost scales with the capacity's numeric value, not just the item count, so a huge target is expensive even with few items.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Coin Change | LeetCode | Medium | 25 mins | teaching |
| 2 | Partition Equal Subset Sum | LeetCode | Medium | 25 mins | teaching |
| 3 | Coin Change II | LeetCode | Medium | 25 mins | consolidation |
| 4 | Target Sum | LeetCode | Medium | 30 mins | consolidation |
| 5 | Combination Sum IV | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Combination Sum IV cleanly in one sitting — handling the order-matters twist on the classic knapsack — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.