Preview — Pro guide
You are seeing a portion of this guide. Sign in and upgrade to unlock the full article, quizzes, and interview answers.
Knapsack DP: 0/1, Unbounded, and Subset Sum Variants
Master all knapsack variants by understanding one mental model: dp[i][w] = best value with first i items and capacity w. Covers 0/1 knapsack, unbounded, bounded, Partition Equal Subset Sum, Coin Change, Target Sum, and the critical forward-vs-reverse iteration insight that distinguishes 0/1 from unbounded.
The Knapsack Mental Model — One Pattern, Many Problems
Every knapsack variant reduces to a single structural question: given items with associated weights (and optionally values), can we fill a capacity W optimally? The state is always dp[i][w] = best result (max value, or boolean reachability, or number of ways) using the first i items with a remaining capacity of exactly w.
Recognizing a knapsack problem in an interview requires seeing past the surface framing. The actual keywords: 'subset,' 'select,' 'fill exactly,' 'maximum/minimum given a constraint,' and most importantly, 'each element used at most once' (0/1) versus 'unlimited' (unbounded). Problems that say 'partition' or 'split the array' are almost always 0/1 knapsack. Problems that say 'coins' or 'unlimited supply' are almost always unbounded knapsack.
The three structural variants and their defining characteristic:
- 0/1 Knapsack: each item can be used at most once. The 1D space optimization iterates capacity in reverse to prevent reusing items.
- Unbounded Knapsack: each item can be used unlimited times. The 1D space optimization iterates capacity forward so updates from the current pass (same item again) feed back in.
- Bounded Knapsack: each item can be used up to k_i times. Reduces to 0/1 by replicating each item k_i times, or solved in O(nW log max_k) with a deque-based sliding window optimization.
The forward-vs-reverse iteration insight is the single most important thing to understand about knapsack. Every other detail is secondary.
What Interviewers Test with Knapsack Problems
Knapsack problems at FAANG are testing two distinct skills. First: can you recognize the reduction? Problems like Partition Equal Subset Sum and Target Sum don't say 'knapsack' — you must see that they're knapsack in disguise. Second: do you know the forward vs reverse iteration rule and can you explain why, not just recite which direction? The answer 'reverse because forward would double-count' is acceptable. The answer 'I just remember reverse for 0/1' is not — follow-up questions will expose the gap. Expect interviewers to flip one condition ('what if items can be reused?') and ask you to adapt your solution on the spot.