# The Knapsack DP Patterns > Master 0/1 and unbounded knapsack DP: the take/skip recurrence, the 1D space trick, and why subset sum, coin change, and target sum are the same problem. Canonical: https://ironclad.academy/dsa/techniques/knapsack-patterns | Difficulty: advanced | Topics: Dynamic Programming, Knapsack, Subset Sum, Coin Change Asked at: Google, Amazon, Meta ## Key takeaways - The 0/1 knapsack state is dp[i][c] = best value using items 0..i with capacity c; the recurrence is take vs. skip. - Compress to O(W) space by iterating capacity right-to-left in 0/1 (prevents reuse) and left-to-right in unbounded (allows reuse). - Subset sum, partition equal subset, coin change, and target sum are knapsack in costume — spot the (index, capacity) state and you have a template. - The "tell" that signals knapsack: pick from a collection to reach a target, each pick is independent, and you want max value, exact reach, or count of ways. - When in doubt about 0/1 vs. unbounded, ask: "can I use this item again?" The answer decides your iteration direction. > **In one line:** Knapsack DP is the art of making take-or-skip decisions over a collection to reach a target — once you see the (index, capacity) state and the take/skip recurrence, you recognize the whole family. You've probably hit a coin change problem and built a solution that worked, but weren't sure *why* the loop went in that direction. Or you solved subset sum and later stared at partition equal subset, feeling like you'd seen it before but couldn't place it. That's because they're all the same problem wearing different clothes. The knapsack family is the most reused DP pattern in interviews. Google, Amazon, and Meta reach for it constantly because it tests whether you can define state cleanly, write a recurrence from first principles, and optimize space — all three skills in one problem. ```mermaid flowchart LR K["Knapsack Family"] K --> A["0/1 Knapsack\n(each item once)"] K --> B["Unbounded Knapsack\n(items reusable)"] A --> C["Subset Sum"] A --> D["Partition Equal Subset"] A --> E["Target Sum"] B --> F["Coin Change"] B --> G["Coin Change II\n(count ways)"] style K fill:#7c5cff,color:#fff style A fill:#22d3ee,color:#0a0a0f style B fill:#22d3ee,color:#0a0a0f style C fill:#00ff9d,color:#0a0a0f style D fill:#00ff9d,color:#0a0a0f style E fill:#00ff9d,color:#0a0a0f style F fill:#00ff9d,color:#0a0a0f style G fill:#00ff9d,color:#0a0a0f ``` The whole family has the same skeleton: items, a capacity, a decision at each item. Nail the base pattern, spot the disguise, apply the template. That's this article. ## The "tell" that signals knapsack Before the mechanics, the recognition. Knapsack problems are hiding in plain sight once you know what to look for. **The signal:** you have a list of numbers (weights, values, integers, coin denominations). There's a target (capacity, sum, goal). You're asked whether you can *reach* the target exactly, *maximize* something within it, or *count ways* to hit it. Each element is considered independently — you either use it or you don't (or you use it as many times as you want). That's it. If you read a problem and think "I'm picking from a pool to hit a number," pause and check if it's knapsack before reaching for anything else. Real examples of the disguise: - *"Can you partition this array into two equal-sum subsets?"* — subset sum in disguise (hit `total/2`). - *"Minimum number of coins to make amount X."* — unbounded knapsack, different question on the same table. - *"How many ways to assign + or – to each number to reach target T?"* — 0/1 knapsack over signed choices. - *"Word break: can you tile a string with dictionary words?"* — unbounded-knapsack-shaped, but order-sensitive: which word applies depends on where you are in the string, so the outer loop must run over positions, not words (the permutation order from the Coin Change II discussion below). ## The base case: 0/1 knapsack Items have weights and values. You have a knapsack of capacity `W`. Each item can go in at most once. Maximize total value. ### State definition `dp[i][c]` = maximum value achievable considering items `0..i` with remaining capacity `c`. That two-coordinate state — *which items have I considered* × *how much capacity remains* — is the fingerprint of this whole family. ### The recurrence: take or skip At item `i` with capacity `c`, you have exactly two choices: 1. **Skip item i:** `dp[i][c] = dp[i-1][c]` — inherit the best from previous items, capacity unchanged. 2. **Take item i** (only if `weights[i] <= c`): `dp[i][c] = values[i] + dp[i-1][c - weights[i]]` — add the value, reduce capacity, look at the rest without item `i`. Take the better of the two: ``` dp[i][c] = max(dp[i-1][c], values[i] + dp[i-1][c - weights[i]]) ``` The table fills left-to-right, top-to-bottom. Each cell only needs the row above it. | | c=0 | c=1 | c=2 | c=3 | c=4 | |---|---|---|---|---|---| | no items | 0 | 0 | 0 | 0 | 0 | | item0 (w=2, v=3) | 0 | 0 | **3** | 3 | 3 | | item1 (w=3, v=4) | 0 | 0 | 3 | **4** | 4 | | item2 (w=4, v=5) | 0 | 0 | 3 | 4 | **5** | Reading the table: with capacity 4, item0 (w=2,v=3) fills at c=2. Item1 (w=3,v=4) fits at c=3 and scores 4, beating item0's 3. Item2 (w=4,v=5) fits exactly at c=4 with value 5 — but note it doesn't beat taking both item0 and item1 if W were larger. Follow the "take vs. skip" comparison cell by cell and the table builds itself. ### The 2D implementation ```python def knapsack_01(weights, values, W): n = len(weights) # dp[i][c]: best value using items 0..i-1 with capacity c dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): w, v = weights[i - 1], values[i - 1] for c in range(W + 1): # skip item i dp[i][c] = dp[i - 1][c] # take item i (only if it fits) if w <= c: dp[i][c] = max(dp[i][c], v + dp[i - 1][c - w]) return dp[n][W] ``` Time: O(n × W). Space: O(n × W). But you can do much better on space. ### The 1D optimization — and WHY it works Every cell in row `i` only looks at row `i-1`. So compress: use a single array and overwrite it. The trick is direction. **Iterate capacity right-to-left.** ```python def knapsack_01_1d(weights, values, W): dp = [0] * (W + 1) for i in range(len(weights)): w, v = weights[i], values[i] # RIGHT TO LEFT — critical for c in range(W, w - 1, -1): dp[c] = max(dp[c], v + dp[c - w]) return dp[W] ``` Why right-to-left? When you update `dp[c]`, the value `dp[c - w]` must still reflect the *previous* item's row — otherwise you're double-counting item `i`. Since `c - w < c`, iterating right-to-left means when you reach index `c`, the value at `c - w` hasn't been touched yet in this pass. It's still "last row." Going left-to-right would overwrite `dp[c - w]` first, letting you "use" item `i` again — which is the unbounded variant, not 0/1. This is one of those things where getting the direction wrong produces subtly wrong answers that pass most small test cases. Burn the reason into memory, not just the direction. ## Unbounded knapsack: items you can reuse Same setup, but each item has no usage limit. Coin denominations are the classic: you can use as many 5-cent coins as you want. The recurrence changes only slightly: ``` dp[i][c] = max(dp[i-1][c], values[i] + dp[i][c - weights[i]]) ^ same row, not i-1 ``` Taking item `i` leaves you free to take item `i` again. In 2D terms, "take" looks at the same row. In 1D terms: **Iterate capacity left-to-right.** ```python def knapsack_unbounded(weights, values, W): dp = [0] * (W + 1) for i in range(len(weights)): w, v = weights[i], values[i] # LEFT TO RIGHT — critical for c in range(w, W + 1): dp[c] = max(dp[c], v + dp[c - w]) return dp[W] ``` Left-to-right means when you compute `dp[c]`, `dp[c - w]` has already been updated in this pass — possibly using item `i` multiple times. That's exactly the behavior you want. ```mermaid flowchart LR subgraph "0/1 — iterate RIGHT to LEFT" direction LR R1["dp[W]"] --> R2["dp[W-1]"] --> R3["..."] --> R4["dp[w]"] note1["dp[c-w] is still last-row\n→ no double-count"] end subgraph "Unbounded — iterate LEFT to RIGHT" direction LR L1["dp[w]"] --> L2["dp[w+1]"] --> L3["..."] --> L4["dp[W]"] note2["dp[c-w] already updated\n→ reuse allowed"] end style R1 fill:#7c5cff,color:#fff style L4 fill:#22d3ee,color:#0a0a0f ``` That one directional difference is the entire mechanical difference between the two variants. Everything else is the same template. ## The disguises ### Subset sum *Can you pick a subset of `nums` that sums to exactly `T`?* Knapsack where `weight[i] = value[i] = nums[i]`, capacity = `T`, answer is boolean: `dp[T] == T`. More idiomatically, use `dp[c]` as a boolean: ```python def can_sum(nums, T): dp = [False] * (T + 1) dp[0] = True # empty subset sums to 0 for num in nums: for c in range(T, num - 1, -1): # 0/1: right-to-left dp[c] = dp[c] or dp[c - num] return dp[T] ``` `dp[c] = True` means "some subset of the items seen so far sums to c." `dp[0] = True` is the base case: the empty subset achieves sum 0. Walk right-to-left for 0/1 (each number used at most once). ### Partition equal subset sum (Leetcode 416) *Given an array, can you split it into two subsets with equal sums?* The total must be even. Then you need one subset summing to `total // 2`. That's subset sum with target `total // 2`. Exact same code, different target. ```python def can_partition(nums): total = sum(nums) if total % 2 != 0: return False return can_sum(nums, total // 2) ``` One insight unlocks the whole thing: you don't need to find *both* subsets. If one subset hits `total/2`, the rest automatically hits `total/2` too. ### Coin change — minimum coins (Leetcode 322) *Given coin denominations and an amount, return the minimum number of coins to make the amount. Coins are unlimited.* Unbounded knapsack. But the question is "minimum coins" not "maximum value," so initialize `dp` to infinity (except `dp[0] = 0`): ```python def coin_change(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 # 0 coins to make amount 0 for coin in coins: for c in range(coin, amount + 1): # unbounded: left-to-right if dp[c - coin] != float('inf'): dp[c] = min(dp[c], 1 + dp[c - coin]) return dp[amount] if dp[amount] != float('inf') else -1 ``` The recurrence: to make amount `c` using this coin, it costs 1 coin plus whatever it costs to make `c - coin`. Minimize. Left-to-right because coins are reusable. ### Coin change II — count ways (Leetcode 518) *Count distinct combinations of coins that sum to amount.* Still unbounded, but `dp[c]` is a count now and the recurrence adds instead of taking min: ```python def change(amount, coins): dp = [0] * (amount + 1) dp[0] = 1 # one way to make 0: use no coins for coin in coins: for c in range(coin, amount + 1): dp[c] += dp[c - coin] return dp[amount] ``` Note the loop order: **outer loop over coins, inner over amounts**. This counts combinations (order doesn't matter: `[1,2]` and `[2,1]` are the same). If you swapped the loops — outer over amounts, inner over coins — you'd count permutations. The outer-coin loop ensures each coin denomination is "introduced" one at a time, so you never count the same combination in different orders. ### Target sum (Leetcode 494) *Assign + or – to each element; count ways to reach target T.* This one is subtler. Let `P` be the sum of numbers assigned +, `N` the sum of numbers assigned –. Then `P + N = total` and `P - N = T`. Solve: `P = (total + T) / 2`. Now count subsets summing to `P` — 0/1 knapsack, count ways: ```python def find_target_sum_ways(nums, target): total = sum(nums) if (total + target) % 2 != 0 or abs(target) > total: return 0 s = (total + target) // 2 dp = [0] * (s + 1) dp[0] = 1 for num in nums: for c in range(s, num - 1, -1): # 0/1: right-to-left dp[c] += dp[c - num] return dp[s] ``` Reducing "assign signs" to "count subsets hitting a derived target" is a common algebraic trick. Once you see it once, you spot it fast. ## Worked problem: partition equal subset Let's trace through `nums = [1, 5, 11, 5]`. Total = 22, target = 11. | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | init | **T** | F | F | F | F | F | F | F | F | F | F | F | | num=1 | T | T | F | F | F | F | F | F | F | F | F | F | | num=5 | T | T | F | F | F | T | T | F | F | F | F | F | | num=11 | T | T | F | F | F | T | T | F | F | F | F | **T** | | num=5 | T | T | F | F | F | T | T | F | F | F | **T** | **T** | After processing `num=11`, `dp[11]` flips to True (you can hit 11 by picking just {11}). After processing the second `num=5`, `dp[10]` also flips (5+5=10) and `dp[11]` stays True. Answer: True — the partition is {11} and {1,5,5}. ## Pitfalls people actually hit **Wrong loop direction.** This is the #1 source of subtle wrong answers. Getting right-to-left and left-to-right confused produces solutions that pass small test cases (where numbers don't repeat the index) and fail large ones. Practice writing the direction comment explicitly every time. **Forgetting `dp[0] = True/1`.** The base case isn't "zero items" — it's "zero capacity can always be achieved by taking nothing." If you initialize the whole array to False/0 without setting `dp[0]`, your recurrence has nothing to propagate from and you'll return False for all inputs. **Using `dp[amount] = -1` for "not possible" and then subtracting from it.** In coin change, initialize to `float('inf')`, not `-1`. Subtracting from `-1` creates garbage values that quietly propagate through the min operations. **Confusing combinations and permutations in count-ways problems.** Outer loop over items gives combinations (each item "introduced" once). Outer loop over capacity gives permutations. Most problems want combinations. Coin Change II explicitly says "number of combinations" — that's the outer-items order. If you get 4 instead of 5 or 5 instead of 4, check your loop order. **Not checking divisibility before subset sum.** In partition equal subset and target sum, invalid inputs (`total % 2 != 0`, `abs(target) > total`) should short-circuit early. Failing to check means you'll index a negative target and either crash or produce nonsense. **Treating zeros in the input carelessly.** A coin or weight of 0 makes inner loops infinite or no-ops depending on how you wrote them. Guard against it explicitly in production code, even if LeetCode inputs don't include zeros. ## When NOT to use knapsack DP Knapsack has O(n × W) complexity. That's fine when both n and W are in the thousands. But it breaks down in a few real scenarios: - **W is huge.** If weights/values are integers up to 10⁹, the DP table is 10⁹ wide. You can't allocate that. Look for a meet-in-the-middle approach (split items in half, enumerate all subset sums for each half, binary search for complements) — O(2^(n/2)), which beats DP when W is astronomical. - **Items aren't independent.** If taking item A forces you to also take item B (dependencies, "group knapsack"), the recurrence needs a different state structure or a tree DP layer. - **You need to *list* the items in the optimal solution, not just the value.** The 1D optimization destroys the reconstruction path. Either keep the full 2D table (and backtrack from `dp[n][W]`) or annotate which items were taken as you fill. - **Greedy is sufficient.** Fractional knapsack (you can take *fractions* of items) is solved optimally by greedy: sort by value/weight ratio, take the best ratio until full. No DP needed. If the problem says fractions are allowed, don't reach for DP. The deeper issue: if you find yourself forcing a problem into knapsack because you don't see another angle, pause. Knapsack requires *independent, discrete choices with a numeric capacity constraint*. If your "items" have side effects on each other, or the "capacity" isn't additive, a different DP formulation will serve you better. See [dp on grids](/dsa/techniques/dp-on-grids) for a related family where the state isn't an item index at all, and [dynamic programming](/dsa/techniques/dynamic-programming) for the broader taxonomy. ## The template to internalize ```python # 0/1 KNAPSACK — each item at most once def knapsack_01_template(items, W, ask="max"): # items: list of (weight, value) tuples # W: capacity # ask: "max" → maximize value; "bool" → can we hit exactly W?; "count" → ways to hit W if ask == "bool": dp = [False] * (W + 1); dp[0] = True for w, v in items: for c in range(W, w - 1, -1): dp[c] = dp[c] or dp[c - w] return dp[W] if ask == "count": dp = [0] * (W + 1); dp[0] = 1 for w, v in items: for c in range(W, w - 1, -1): dp[c] += dp[c - w] return dp[W] # ask == "max" (default) dp = [0] * (W + 1) for w, v in items: for c in range(W, w - 1, -1): dp[c] = max(dp[c], v + dp[c - w]) return dp[W] # UNBOUNDED KNAPSACK — items reusable def knapsack_unbounded_template(items, W, ask="max"): if ask == "min": dp = [float('inf')] * (W + 1); dp[0] = 0 for w, v in items: for c in range(w, W + 1): if dp[c - w] != float('inf'): dp[c] = min(dp[c], v + dp[c - w]) return dp[W] if dp[W] != float('inf') else -1 if ask == "count": dp = [0] * (W + 1); dp[0] = 1 for w, v in items: for c in range(w, W + 1): dp[c] += dp[c - w] return dp[W] # ask == "max" dp = [0] * (W + 1) for w, v in items: for c in range(w, W + 1): dp[c] = max(dp[c], v + dp[c - w]) return dp[W] ``` The whole family, one row per problem: | Problem | 0/1 or unbounded | Direction | `dp[c]` means | `dp[0]` init | Rest init | Combine | |---|---|---|---|---|---|---| | 0/1 knapsack (max value) | 0/1 | right-to-left | best value within capacity `c` | 0 | 0 | `max` | | Unbounded knapsack (max value) | unbounded | left-to-right | best value within capacity `c` | 0 | 0 | `max` | | Subset sum | 0/1 | right-to-left | some subset sums to exactly `c` | `True` | `False` | `or` | | Partition equal subset (LC 416) | 0/1 | right-to-left | subset hits `c`; target `total // 2` | `True` | `False` | `or` | | Coin change (LC 322) | unbounded | left-to-right | min coins to make `c` | 0 | `inf` | `min(dp[c], 1 + dp[c-w])` | | Coin change II (LC 518) | unbounded | left-to-right | combinations summing to `c` | 1 | 0 | `+=` | | Target sum (LC 494) | 0/1 | right-to-left | ways to hit `c`; target `(total + T) // 2` | 1 | 0 | `+=` | The only four things that change between variants: (1) 0/1 vs. unbounded → iteration direction; (2) maximize, minimize, boolean, or count → how you combine `dp[c]` with `dp[c - w]`; (3) initial value of `dp[0]`; (4) initial value of all other cells. Everything else — the outer loop over items, the inner loop over capacity, the conditional on `c >= w` — stays identical. --- If this is your first time reading about knapsack, go implement coin change (Leetcode 322) and partition equal subset (Leetcode 416) back-to-back. The muscle memory of writing the loop direction correctly twice in a row does more than rereading this article three times. Then try target sum (Leetcode 494) for the algebraic reduction trick. Those three problems cover the whole family. For the broader DP landscape, [dynamic programming](/dsa/techniques/dynamic-programming) has the full framework for identifying DP problems and defining states. For the 2D cousin of this pattern — where your state is a grid position rather than an index+capacity — see [dp on grids](/dsa/techniques/dp-on-grids). And if any of these problems arrive during a system design that involves scheduling or prioritization, [heaps](/dsa/structures/heap) often pair with DP to efficiently track the current best candidate. ## Frequently asked questions Q: What is the difference between 0/1 knapsack and unbounded knapsack? A: In 0/1 knapsack each item can be used at most once — you either take it or skip it. In unbounded knapsack you can take any item as many times as you want. This single difference changes the iteration direction in the 1D optimization: 0/1 iterates capacity backwards (to prevent reusing an item in the same pass), unbounded iterates forwards (to allow reusing). Q: Why do you iterate capacity backwards in 0/1 knapsack but forwards in unbounded knapsack? A: When you compress the 2D DP table to 1D, you reuse the same array across items. For 0/1 knapsack, iterating capacity right-to-left means dp[c] is updated from dp[c - weight], which still holds the value from the previous item's row — so you never count the same item twice. For unbounded knapsack, iterating left-to-right means dp[c - weight] has already been updated in this item's pass, which is exactly what you want — it reflects taking the current item multiple times. Q: How do I recognize a knapsack problem in disguise? A: Look for these tells: you have a collection of items/numbers and a target value (capacity). You're asked whether you can reach the target exactly, or the max value achievable within the target, or the number of ways to reach it. The 'index + remaining capacity' state shape is the giveaway. Subset sum, coin change, partition equal subset, and target sum are all knapsack in costume. Q: What is the time and space complexity of knapsack DP? A: Both 0/1 and unbounded knapsack run in O(n × W) time where n is the number of items and W is the capacity. The 2D table needs O(n × W) space. The 1D optimization reduces space to O(W) by overwriting in-place, since you only ever look at the previous row. Q: What is "subset sum" and how does it relate to knapsack? A: Subset sum asks: given an array of integers, can you pick a subset that adds up to exactly T? It is 0/1 knapsack where every item has weight equal to its value, and the goal is to hit capacity T exactly (boolean outcome rather than max value). The same table, the same iteration, the same space optimization — just a different question you ask of the cells.