0/1 Knapsack (DP)
Choose/skip decisions over items with capacity; tabulate optimal value for subproblems.
Subset sum, partition equal subset sum, target sum, coin change, rod cutting.
The DP table has one row per item (n) and one column per capacity (m = W), each filled in O(1). Space can be compressed to O(m) by keeping only the previous row.
0/1 knapsack is the prototype for 'decide include/exclude over n items with a capacity constraint, maximizing value'. The state is (item index, remaining capacity), the transition is max(skip = dp[i+1][c], take = dp[i+1][c - w[i]] + v[i]). Time and space are O(n * C); space can drop to O(C) by iterating capacity from high to low to avoid reusing the same item.
Many problems are knapsack in disguise. Subset sum: values = weights, ask if any subset hits exactly the target. Partition equal subset sum: subset sum with target = total/2. Coin change (unbounded): like knapsack but items have unlimited copies, so iterate capacity low-to-high. Target sum: assign +/- to each number, transform to subset sum via algebra (count subsets summing to (total + target) / 2).
The 1D space optimization is the most common interview ask. Direction matters: iterate capacity high-to-low for 0/1 (each item used at most once); low-to-high for unbounded (each item reusable). Reversing the iteration direction silently changes the semantics — a subtle bug.
Iterating capacity from high to low in the 1D rollover prevents using the same item twice in 0/1 knapsack; reversing the direction enables unbounded knapsack — the same recurrence, different iteration order, different problem.
- Confusing 0/1 vs unbounded variants and getting the loop direction wrong, double-counting items or missing valid combinations.
- For 'count number of ways' variants, initializing dp[0] = 0 instead of dp[0] = 1 (empty subset is one valid way to make target 0).
- In target sum, forgetting to check that (total + target) is even and non-negative before dividing — otherwise no valid subset exists.
- Mixing 'maximize value' (take max) with 'count ways' (take sum) recurrences.
- Iterating items as the inner loop when you want unbounded behavior over permutations (combination sum IV) vs combinations (coin change count) — the loop nesting changes the meaning.
- 0/1 knapsack: max value with each item at most once.
- Unbounded knapsack: coin change (min coins), rod cutting, integer break.
- Subset sum / partition equal subset sum: knapsack with capacity = target.
- Target sum / +- assignment: transform to subset sum count.
- Bounded knapsack (limited copies): expand into 0/1 with copies, or binary decomposition.
// 0/1 knapsack: each item used at most once
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int s = target; s >= num; s--) {
dp[s] = dp[s] || dp[s - num];
}
}
return dp[target];Problems using this pattern
6Easiest first · Blind 75 above NeetCode 150