Knapsack Pattern
The Knapsack Family
All knapsack variants share the same core structure: items with weights and values, a capacity constraint, and an optimisation goal. The key distinction is how many times each item can be used.
KNAPSACK VARIANTS: 0/1 Knapsack: Each item used 0 or 1 times Unbounded Knapsack: Each item used unlimited times Bounded Knapsack: Each item used at most k times Subset Sum: Existence version — can we reach exactly target? Partition: Split into two equal-sum groups ALL SHARE: Items: weight[i], value[i] (or just nums[i] for subset problems) Capacity W (or target T) State: dp[i][w] = best answer using first i items with capacity w KEY QUESTION: "Can each item be reused?" YES → Unbounded → iterate LEFT TO RIGHT in 1D optimisation NO → 0/1 → iterate RIGHT TO LEFT in 1D optimisation
Variant 1: 0/1 Knapsack
Each item used at most once. Classic two-choice DP: skip or take.
STATE: dp[i][w] = max value using items[0..i-1] with capacity w
RECUR: dp[i][w] = dp[i-1][w] ← skip item i
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
values[i-1] + dp[i-1][w-weights[i-1]]) ← take item i
BASE: dp[0][w] = 0 for all w (no items → no value)
FILL: Row by row (i outer 1→n, w inner 0→W)
ANSWER: dp[n][W]
ITEMS: weights=[2,3,4,5], values=[3,4,5,6], W=5
2D TABLE:
w=0 w=1 w=2 w=3 w=4 w=5
i=0 [ 0, 0, 0, 0, 0, 0 ] ← no items
i=1 [ 0, 0, 3, 3, 3, 3 ] ← item(w=2,v=3)
i=2 [ 0, 0, 3, 4, 4, 7 ] ← item(w=3,v=4)
i=3 [ 0, 0, 3, 4, 5, 7 ] ← item(w=4,v=5)
i=4 [ 0, 0, 3, 4, 5, 7 ] ← item(w=5,v=6)
dp[2][5]: skip item2(w=3,v=4) → dp[1][5]=3
take item2 → 4+dp[1][5-3]=4+dp[1][2]=4+3=7 ← take!
dp[2][5] = 7 ✓ (items w=2+w=3, values 3+4)
1D Space Optimisation — RIGHT TO LEFT
OBSERVATION: dp[i][w] only uses row i-1.
Replace 2D dp[n+1][W+1] with 1D dp[W+1].
KEY: iterate w from W DOWN TO weights[i].
RIGHT TO LEFT ensures dp[w-weight] still holds value from row i-1
(not yet updated for current item i).
1D TRACE for same items, W=5:
Initial dp: [0, 0, 0, 0, 0, 0]
Item 0 (w=2, v=3): iterate w=5 down to 2
w=5: dp[5]=max(0,3+dp[3])=max(0,3+0)=3
w=4: dp[4]=max(0,3+dp[2])=max(0,3+0)=3
w=3: dp[3]=max(0,3+dp[1])=max(0,3+0)=3
w=2: dp[2]=max(0,3+dp[0])=max(0,3+0)=3
dp: [0, 0, 3, 3, 3, 3]
Item 1 (w=3, v=4): iterate w=5 down to 3
w=5: dp[5]=max(3,4+dp[2])=max(3,4+3)=7
w=4: dp[4]=max(3,4+dp[1])=max(3,4+0)=4
w=3: dp[3]=max(3,4+dp[0])=max(3,4+0)=4
dp: [0, 0, 3, 4, 4, 7]
Item 2 (w=4, v=5): iterate w=5 down to 4
w=5: dp[5]=max(7,5+dp[1])=max(7,5+0)=7
w=4: dp[4]=max(4,5+dp[0])=max(4,5+0)=5
dp: [0, 0, 3, 4, 5, 7]
Item 3 (w=5, v=6): iterate w=5 down to 5
w=5: dp[5]=max(7,6+dp[0])=max(7,6+0)=7
dp: [0, 0, 3, 4, 5, 7]
Answer: dp[5] = 7 ✓
Variant 2: Unbounded Knapsack
Each item used unlimited times.
STATE: dp[w] = max value achievable with capacity w (using any items, unlimited)
RECUR: dp[w] = max(dp[w], values[i] + dp[w-weights[i]])
for each item i where weights[i] <= w
BASE: dp[0] = 0
FILL: w from 1 to W (LEFT TO RIGHT — allows reuse)
ANSWER: dp[W]
WHY LEFT TO RIGHT ALLOWS REUSE:
When computing dp[w], dp[w-weight] was already updated for item i.
So dp[w-weight] might already include item i → dp[w] adds item i again.
This self-reference is the mechanism for unlimited use.
ITEMS: weights=[1,3,4], values=[1,4,5], W=7
1D TRACE (iterate w left to right, for each w try all items):
dp: [0, 0, 0, 0, 0, 0, 0, 0]
w=1: item(w=1,v=1): 1+dp[0]=1. dp[1]=1
w=2: item(w=1,v=1): 1+dp[1]=2. dp[2]=2
w=3: item(w=1,v=1): 1+dp[2]=3; item(w=3,v=4): 4+dp[0]=4. dp[3]=4
w=4: item(w=1,v=1): 1+dp[3]=5; item(w=3,v=4): 4+dp[1]=5; item(w=4,v=5): 5+dp[0]=5. dp[4]=5
w=5: item(w=1,v=1): 1+dp[4]=6; item(w=3,v=4): 4+dp[2]=6; item(w=4,v=5): 5+dp[1]=6. dp[5]=6
w=6: item(w=1,v=1): 1+dp[5]=7; item(w=3,v=4): 4+dp[3]=8; item(w=4,v=5): 5+dp[2]=7. dp[6]=8
w=7: item(w=1,v=1): 1+dp[6]=9; item(w=3,v=4): 4+dp[4]=9; item(w=4,v=5): 5+dp[3]=9. dp[7]=9
Answer: dp[7]=9 ← using item(w=3,v=4) twice + item(w=1,v=1) once: 4+4+1=9 ✓
ALTERNATIVE FORMULATION (loop order swapped):
for w in 1..W:
for each item i: dp[w] = max(dp[w], values[i]+dp[w-weights[i]])
This also works and is equivalent.
Variant 3: Subset Sum
Can a subset of the given array sum to exactly target T? (0/1 — each element once)
STATE: dp[w] = can we reach sum exactly w using elements so far?
BASE: dp[0] = true (empty subset sums to 0)
dp[w] = false for w > 0 initially
RECUR: For each number num:
iterate w from T DOWN TO num:
dp[w] = dp[w] OR dp[w-num]
(right to left = 0/1: each number used at most once)
ANSWER: dp[T]
TRACE for nums=[3,1,5,9], T=9:
Initial: dp=[T,F,F,F,F,F,F,F,F,F] (index 0..9)
num=3: w=9→3
dp[3]=dp[3]|dp[0]=F|T=T
dp=[T,F,F,T,F,F,F,F,F,F]
num=1: w=9→1
dp[4]=dp[4]|dp[3]=F|T=T
dp[1]=dp[1]|dp[0]=F|T=T
dp=[T,T,F,T,T,F,F,F,F,F]
num=5: w=9→5
dp[9]=dp[9]|dp[4]=F|T=T ← 1+3+5=9 ✓
dp[8]=dp[8]|dp[3]=F|T=T ← 3+5=8 ✓
dp[6]=dp[6]|dp[1]=F|T=T ← 1+5=6 ✓
dp[5]=dp[5]|dp[0]=F|T=T ← 5 ✓
dp=[T,T,F,T,T,T,T,F,T,T]
Answer: dp[9]=true ✓ (subset {1,3,5} sums to 9)
Variant 4: Partition Equal Subset Sum
Split array into two subsets with equal sum.
KEY INSIGHT:
If total sum is odd → impossible (can't split evenly).
If total sum is even → find subset summing to totalSum/2.
This is exactly 0/1 Subset Sum with target = totalSum/2.
TRACE for nums=[1,5,11,5]:
totalSum = 22, target = 11
Run 0/1 Subset Sum for target=11:
dp = [T,F,F,...,F] (length 12)
num=1: dp[1]=T
num=5: dp[6]=dp[1]=T; dp[5]=dp[0]=T
num=11: dp[11]=dp[0]=T ← found! dp[11]=true
Can split: {11} and {1,5,5} — both sum to 11 ✓
Complete Implementations
1import java.util.*;
2
3public class KnapsackPatterns {
4
5 // ── 0/1 Knapsack — 2D (full table) ──────────────────────────────
6 public static int knapsack01_2D(int[] weights, int[] values, int W) {
7 int n = weights.length;
8 int[][] dp = new int[n+1][W+1];
9
10 for (int i=1; i<=n; i++) {
11 for (int w=0; w<=W; w++) {
12 dp[i][w] = dp[i-1][w]; // Skip item i
13 if (weights[i-1] <= w) {
14 dp[i][w] = Math.max(dp[i][w],
15 values[i-1] + dp[i-1][w-weights[i-1]]); // Take item i
16 }
17 }
18 }
19 return dp[n][W];
20 }
21
22 // ── 0/1 Knapsack — 1D optimised, RIGHT TO LEFT ──────────────────
23 public static int knapsack01_1D(int[] weights, int[] values, int W) {
24 int[] dp = new int[W+1];
25
26 for (int i=0; i<weights.length; i++) {
27 // RIGHT TO LEFT: each item used at most once
28 for (int w=W; w>=weights[i]; w--) {
29 dp[w] = Math.max(dp[w], values[i] + dp[w-weights[i]]);
30 }
31 }
32 return dp[W];
33 }
34
35 // ── Unbounded Knapsack — 1D, LEFT TO RIGHT ──────────────────────
36 public static int knapsackUnbounded(int[] weights, int[] values, int W) {
37 int[] dp = new int[W+1];
38
39 for (int w=1; w<=W; w++) {
40 // LEFT TO RIGHT: each item usable unlimited times
41 for (int i=0; i<weights.length; i++) {
42 if (weights[i] <= w) {
43 dp[w] = Math.max(dp[w], values[i] + dp[w-weights[i]]);
44 }
45 }
46 }
47 return dp[W];
48 }
49
50 // ── Subset Sum — 1D boolean, RIGHT TO LEFT ──────────────────────
51 public static boolean subsetSum(int[] nums, int target) {
52 boolean[] dp = new boolean[target+1];
53 dp[0] = true; // Empty subset
54
55 for (int num : nums) {
56 // RIGHT TO LEFT: each number used at most once
57 for (int w=target; w>=num; w--) {
58 dp[w] = dp[w] || dp[w-num];
59 }
60 }
61 return dp[target];
62 }
63
64 // ── Partition Equal Subset Sum ───────────────────────────────────
65 public static boolean canPartition(int[] nums) {
66 int total = Arrays.stream(nums).sum();
67 if (total % 2 != 0) return false; // Odd sum: impossible
68 return subsetSum(nums, total / 2);
69 }
70
71 // ── Count Subsets with Given Sum ─────────────────────────────────
72 public static int countSubsets(int[] nums, int target) {
73 int[] dp = new int[target+1];
74 dp[0] = 1; // One way to reach sum 0: empty subset
75
76 for (int num : nums) {
77 // RIGHT TO LEFT: each number used at most once
78 for (int w=target; w>=num; w--) {
79 dp[w] += dp[w-num];
80 }
81 }
82 return dp[target];
83 }
84
85 // ── Coin Change (min coins) — Unbounded, LEFT TO RIGHT ──────────
86 public static int coinChange(int[] coins, int amount) {
87 int[] dp = new int[amount+1];
88 Arrays.fill(dp, amount+1); // Sentinel
89 dp[0] = 0;
90
91 for (int w=1; w<=amount; w++) {
92 for (int coin : coins) {
93 if (coin <= w) {
94 dp[w] = Math.min(dp[w], 1 + dp[w-coin]);
95 }
96 }
97 }
98 return dp[amount] > amount ? -1 : dp[amount];
99 }
100
101 // ── Coin Change II (count ways) — Unbounded ──────────────────────
102 public static int coinChangeWays(int[] coins, int amount) {
103 int[] dp = new int[amount+1];
104 dp[0] = 1; // One way to make 0: use no coins
105
106 // NOTE: outer loop over coins, inner over amounts
107 // This avoids counting permutations as different combinations
108 for (int coin : coins) {
109 for (int w=coin; w<=amount; w++) { // LEFT TO RIGHT
110 dp[w] += dp[w-coin];
111 }
112 }
113 return dp[amount];
114 }
115
116 public static void main(String[] args) {
117 int[] w={2,3,4,5}, v={3,4,5,6};
118 System.out.println("0/1 Knapsack 2D (W=5): " + knapsack01_2D(w,v,5)); // 7
119 System.out.println("0/1 Knapsack 1D (W=5): " + knapsack01_1D(w,v,5)); // 7
120 System.out.println("Unbounded (W=7): " +
121 knapsackUnbounded(new int[]{1,3,4}, new int[]{1,4,5}, 7)); // 9
122 System.out.println("Subset Sum [3,1,5,9]=9: " + subsetSum(new int[]{3,1,5,9}, 9)); // true
123 System.out.println("Subset Sum =11: " + subsetSum(new int[]{3,1,5,9}, 11)); // false
124 System.out.println("Partition [1,5,11,5]: " + canPartition(new int[]{1,5,11,5})); // true
125 System.out.println("Count subsets =5: " + countSubsets(new int[]{1,2,3,4},5)); // 3
126 System.out.println("Coin Change min(6): " + coinChange(new int[]{1,3,4},6)); // 2
127 System.out.println("Coin Change ways(5): " + coinChangeWays(new int[]{1,2,5},5)); // 4
128 }
129}Output:
0/1 Knapsack 2D (W=5): 7
0/1 Knapsack 1D (W=5): 7
Unbounded (W=7): 9
Subset Sum [3,1,5,9]=9: true
Subset Sum =11: false
Partition [1,5,11,5]: true
Count subsets=5: 3
Coin Change min(6): 2
Coin Change ways(5): 4
The Iteration Direction Rule
The single most important rule in knapsack DP:
CAN EACH ITEM BE REUSED?
NO (0/1) → iterate w RIGHT TO LEFT (W down to weight[i])
"Protects past decisions from being reused"
YES (unbounded) → iterate w LEFT TO RIGHT (weight[i] up to W)
"Allows current item to build on itself"
WHY THIS WORKS:
For 0/1 (right to left):
dp[w] = max(dp[w], val[i] + dp[w-wt[i]])
When reading dp[w-wt[i]]: it hasn't been updated for item i yet
(since we're going right to left and w-wt[i] < w).
So dp[w-wt[i]] still reflects item i-1's decisions. ✓
For unbounded (left to right):
dp[w] = max(dp[w], val[i] + dp[w-wt[i]])
When reading dp[w-wt[i]]: it WAS already updated for item i
(since w-wt[i] < w and we processed smaller w first).
So dp[w-wt[i]] may already include item i → item i used again. ✓
MEMORY AID:
0/1 = "protect the past" → go right to left (don't look back at updated values)
Unbounded = "use freely" → go left to right (build on already-updated values)
Coin Change II: Why Outer Loop Matters
COUNT COMBINATIONS vs COUNT PERMUTATIONS:
WRONG (counts permutations):
for w in 1..amount:
for coin in coins:
dp[w] += dp[w-coin]
"12" and "21" both counted → overcounts
CORRECT (counts combinations only):
for coin in coins: ← outer: each coin
for w in coin..amount: ← inner: amounts
dp[w] += dp[w-coin]
By fixing which coin is processed, we ensure each
COMBINATION is counted exactly once (not its permutations).
TRACE for coins=[1,2,5], amount=5:
Correct (combinations):
Process coin=1: dp=[1,1,1,1,1,1] (ways using only coin 1)
Process coin=2: dp=[1,1,2,2,3,3] (add ways using coins 1,2)
Process coin=5: dp=[1,1,2,2,3,4] (add way using coin 5: 5)
dp[5] = 4 combinations: {1,1,1,1,1},{1,1,1,2},{1,2,2},{5} ✓
Knapsack Variant Cheat Sheet
VARIANT USE EACH GOAL DIRECTION INIT ANSWER
ITEM
──────────────────────────────────────────────────────────────────────
0/1 Knapsack Once max val R→L dp[0]=0 dp[W]
Unbounded Unlimited max val L→R dp[0]=0 dp[W]
Subset Sum Once exists? R→L (bool) dp[0]=T dp[T]
Count subsets Once count R→L dp[0]=1 dp[T]
Coin Change min Unlimited min coins L→R dp[0]=0, dp[A]
rest=INF
Coin Change II Unlimited count L→R dp[0]=1 dp[A]
combos (outer:coin)
Partition Once exists? R→L dp[0]=T dp[sum/2]
Space Optimisation Summary
0/1 KNAPSACK: O(n×W) → O(W) Replace 2D dp[n+1][W+1] with 1D dp[W+1] Iterate W down to weight[i] for each item UNBOUNDED KNAPSACK: Already O(W) in natural formulation dp[w] = max over all items: val[i] + dp[w-wt[i]] Iterate w from 1 to W SUBSET SUM / COUNT SUBSETS: O(n×T) → O(T) Same as 0/1 Knapsack: right-to-left inner loop COIN CHANGE: Already O(amount) in natural formulation SPACE CANNOT BE REDUCED BELOW O(W) or O(T): The entire 1D array is always needed. Unlike 1D DP (Fibonacci: O(1) with 2 variables), knapsack needs all W+1 cells at every step.
Complexity Summary
| Problem | Time | Space (2D) | Space (1D) |
|---|---|---|---|
| 0/1 Knapsack | O(n×W) | O(n×W) | O(W) |
| Unbounded Knapsack | O(n×W) | — | O(W) |
| Subset Sum | O(n×T) | O(n×T) | O(T) |
| Partition Equal Subset | O(n×S/2) | O(n×S/2) | O(S/2) |
| Count Subsets | O(n×T) | O(n×T) | O(T) |
| Coin Change (min) | O(A×k) | — | O(A) |
| Coin Change II | O(A×k) | — | O(A) |
Common Mistakes
0/1 Knapsack 1D: iterating left to right instead of right to left. Left to right means dp[w-weight] might have already been updated for the current item — the item is counted twice, giving unbounded-knapsack behaviour instead of 0/1. Always iterate right to left for 0/1 knapsack. Mnemonic: "Once per item → go right to left."
Coin Change II: swapping outer and inner loop order. Putting the amount loop outside and the coin loop inside counts ordered sequences (permutations). For example, making 4 with coins [1,2]: 1+1+2 and 1+2+1 and 2+1+1 are counted as three different ways. The correct approach puts coins in the outer loop — once a coin is processed, its contribution is fixed, so only unordered combinations are counted.
Subset Sum: initialising dp[0] = false. dp[0] = true represents "the empty subset sums to 0 — always possible." Without this anchor, the entire dp array remains false. This base case is the foundation of all subset-style DP.
Partition: not checking for odd total sum first. If the total sum is odd, it cannot be split into two equal halves — return false immediately. Running the DP with target = total/2 using integer division (e.g., 7/2=3 in integer arithmetic) would silently give a wrong answer.
Sentinel for minimum problems. For Coin Change (minimum), use amount+1 as the initial sentinel, not INT_MAX. Adding 1 to INT_MAX overflows to a negative number. amount+1 is safe: it's larger than any valid answer (can't need more than amount coins of denomination 1), and 1 + (amount+1) = amount+2 still compares correctly.
Interview Questions
Q: What is the single biggest difference between 0/1 Knapsack and Unbounded Knapsack implementations?
The iteration direction for the capacity loop in the 1D optimised version. 0/1 Knapsack iterates right to left (W down to weight[i]) — reading dp[w-weight] before it's updated for the current item, so each item appears at most once. Unbounded Knapsack iterates left to right (weight[i] up to W) — reading dp[w-weight] after it may have been updated for the current item, allowing the current item to contribute multiple times. Everything else (recurrence, initialisation, answer location) is identical.
Q: Coin Change II asks for the number of combinations, not permutations. How does the loop structure achieve this?
By putting the coins loop on the outside and the amount loop on the inside. This ensures that when processing coin c, all combinations using only coins processed so far are computed. Each combination is counted exactly once — in a canonical order determined by coin processing order. If the loops were reversed (amount outside, coins inside), each ordering of the same coins would be counted separately, giving permutations.
Q: How would you modify 0/1 Knapsack to output which items were selected, not just the maximum value?
Solve the 2D DP (or keep the full 2D table). After computing dp[n][W], backtrack: starting at dp[n][W], if dp[i][w] != dp[i-1][w], item i was selected — record it, subtract its weight, and move to dp[i-1][w-weight[i-1]]. If dp[i][w] == dp[i-1][w], item i was skipped — move to dp[i-1][w]. Repeat until i=0. With the 1D space-optimised version, you cannot directly backtrack — you'd need to re-run with the 2D table or store a separate choice array during the DP.
Summary
The knapsack family solves "choose items under a constraint" problems. The key structural variable is whether each item can be reused.
The single decision that determines everything:
| 0/1 Knapsack | Unbounded Knapsack | |
|---|---|---|
| Each item used | At most once | Unlimited times |
| 1D inner loop | Right to left | Left to right |
| Mechanism | Reads pre-item values | Reads post-item values |
Six variants and their mappings:
| Variant | Maps to | Key change |
|---|---|---|
| 0/1 Knapsack | base | max value, right to left |
| Unbounded Knapsack | base | max value, left to right |
| Subset Sum | 0/1 | boolean dp, OR operation |
| Count Subsets | 0/1 | count dp, += operation |
| Partition | 0/1 Subset Sum | target = totalSum/2 |
| Coin Change min | Unbounded | minimum dp, sentinel+1 init |
| Coin Change ways | Unbounded | count combos, outer=coins |
Space: always O(W) or O(T) with the 1D optimisation. Cannot reduce further — entire 1D array needed at every step.
In the next topic you will explore Longest Common Subsequence (LCS) — the foundational string DP pattern with edit distance, shortest common supersequence, and print-path extensions.
0/1 Knapsack: when optimising from 2D to 1D, why must the capacity loop go RIGHT TO LEFT (W down to weights[i])?