Knapsack problems are the most important dynamic programming pattern class. Mastering 0/1 knapsack, unbounded knapsack, and their variants (subset sum, coin change, partition equal subset) unlocks a wide range of interview problems at top tech companies.
0/1 Knapsack: The Template
Problem: given items with weights and values, and capacity W,
maximize total value without exceeding capacity.
Each item can be used at most once (0/1).
def knapsack_01(weights: list, values: list, W: int) -> int:
n = len(weights)
# dp[i][w] = max value using first i items with capacity w
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w_i, v_i = weights[i-1], values[i-1]
for w in range(W + 1):
# Option 1: skip item i
dp[i][w] = dp[i-1][w]
# Option 2: take item i (if it fits)
if w >= w_i:
dp[i][w] = max(dp[i][w], dp[i-1][w - w_i] + v_i)
return dp[n][W]
# Space optimization to O(W): iterate weights in reverse
def knapsack_01_optimized(weights, values, W):
dp = [0] * (W + 1)
for w_i, v_i in zip(weights, values):
for w in range(W, w_i - 1, -1): # ← REVERSE: prevents using same item twice
dp[w] = max(dp[w], dp[w - w_i] + v_i)
return dp[W]
# Time: O(n × W), Space: O(W)Pattern: Subset Sum
def canPartition(nums: list[int]) -> bool:
"""LC 416: partition array into two equal-sum subsets"""
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
# dp[w] = can we form sum w using some subset?
dp = [False] * (target + 1)
dp[0] = True # empty subset sums to 0
for num in nums:
for w in range(target, num - 1, -1): # reverse to avoid reuse
dp[w] = dp[w] or dp[w - num]
return dp[target]
# Generalization: find subset summing to target
def subsetSum(nums: list[int], target: int) -> bool:
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for w in range(target, num - 1, -1):
if dp[w - num]:
dp[w] = True
return dp[target]Pattern: Unbounded Knapsack (items reusable)
def knapsack_unbounded(weights, values, W):
"""Each item can be used unlimited times"""
dp = [0] * (W + 1)
for w_i, v_i in zip(weights, values):
for w in range(w_i, W + 1): # ← FORWARD: allows reusing same item
dp[w] = max(dp[w], dp[w - w_i] + v_i)
return dp[W]
# Key insight: reverse loop = 0/1 (each item once)
# forward loop = unbounded (item reusable)Pattern: Coin Change (Minimum Coins)
def coinChange(coins: list[int], amount: int) -> int:
"""LC 322: fewest coins to make amount — unbounded knapsack variant"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for amt in range(coin, amount + 1): # forward: coins reusable
if dp[amt - coin] != float('inf'):
dp[amt] = min(dp[amt], dp[amt - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
def coinChangeWays(coins: list[int], amount: int) -> int:
"""LC 518: number of combinations to make amount"""
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make 0: use no coins
for coin in coins:
for amt in range(coin, amount + 1):
dp[amt] += dp[amt - coin]
return dp[amount]
# NOTE: outer loop is coins, inner is amount → each combination counted once
# If outer loop were amount and inner coins → permutations (order matters)Pattern: Target Sum (LC 494)
def findTargetSumWays(nums: list[int], target: int) -> int:
"""Assign + or - to each num to reach target"""
# Let P = set of positives, N = set of negatives
# P - N = target, P + N = total
# → 2P = target + total → P = (target + total) / 2
# Count subsets summing to (target + total) // 2
total = sum(nums)
if (total + target) % 2 != 0 or abs(target) > total:
return 0
subset_target = (total + target) // 2
dp = [0] * (subset_target + 1)
dp[0] = 1
for num in nums:
for w in range(subset_target, num - 1, -1):
dp[w] += dp[w - num]
return dp[subset_target]Pattern: Last Stone Weight II (LC 1049)
def lastStoneWeightII(stones: list[int]) -> int:
"""Minimize |sum(group1) - sum(group2)| = minimize 2×sum(group1) - total"""
# Equivalent to: find subset sum closest to total//2
total = sum(stones)
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for s in stones:
for w in range(target, s - 1, -1):
dp[w] = dp[w] or dp[w - s]
# Find largest achievable sum ≤ target
for s in range(target, -1, -1):
if dp[s]:
return total - 2 * sPattern: 2D Knapsack (Ones and Zeroes, LC 474)
def findMaxForm(strs: list[str], m: int, n: int) -> int:
"""Largest subset with at most m zeros and n ones — 2D knapsack"""
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
zeros = s.count('0')
ones = len(s) - zeros
# Reverse both dimensions (0/1: each string used once)
for i in range(m, zeros - 1, -1):
for j in range(n, ones - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
return dp[m][n]Pattern: Bounded Knapsack (each item limited count)
def knapsack_bounded(weights, values, counts, W):
"""Each item i can be used at most counts[i] times"""
dp = [0] * (W + 1)
for w_i, v_i, c_i in zip(weights, values, counts):
# Binary grouping: represent count as 1 + 2 + 4 + ... + remainder
# Reduces to 0/1 knapsack with O(sum(log c_i)) groups
groups = []
k = 1
remaining = c_i
while k 0:
groups.append((remaining * w_i, remaining * v_i))
# Now apply 0/1 knapsack for each group
for gw, gv in groups:
for w in range(W, gw - 1, -1):
dp[w] = max(dp[w], dp[w - gw] + gv)
return dp[W]Knapsack Variant Recognition
| Problem Signal | Variant | Loop Direction |
|---|---|---|
| “each item used at most once” | 0/1 Knapsack | Reverse inner loop |
| “unlimited supply of each item” | Unbounded | Forward inner loop |
| “each item limited to k times” | Bounded | Binary grouping → 0/1 |
| “can we achieve exactly X” | Subset Sum (bool) | Reverse, OR updates |
| “how many ways to make X” | Count combinations | Forward (coins outer) |
| “minimize coins/items to make X” | Coin Change | Forward, min updates |
Key Interview Tips
- The one rule to remember: Reverse inner loop for 0/1 (prevents reusing the item in the same pass). Forward inner loop for unbounded (enables reusing the item). This single distinction separates all knapsack variants.
- Outer loop order matters for counting: Coin change COMBINATIONS (outer = items, inner = amounts) counts each combination once. Coin change PERMUTATIONS (outer = amounts, inner = items) counts each ordering separately.
- Subset sum as boolean knapsack: Replace max() with OR, and value with 1. The DP recurrence is identical — this mental mapping unlocks LC 416, 494, 1049, and similar problems.
- Space optimization: The 2D DP table always collapses to a 1D array because dp[i][w] only depends on dp[i-1][w] and dp[i-1][w-w_i]. Start by writing the 2D solution for clarity, then optimize to 1D.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the key difference between 0/1 knapsack and unbounded knapsack in DP?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The only implementation difference is the direction of the inner loop. In 0/1 knapsack (each item used at most once), the inner loop iterates from W down to the item’s weight: “for w in range(W, weight-1, -1)”. This reverse iteration ensures that when computing dp[w], the value dp[w-weight] reflects the state before the current item was considered, preventing the item from being used more than once. In unbounded knapsack (items reusable), the inner loop iterates forward from the item’s weight to W: “for w in range(weight, W+1)”. The forward direction means dp[w-weight] already includes the current item, allowing it to be used again.”
}
},
{
“@type”: “Question”,
“name”: “How do you recognize that a problem is a subset sum or knapsack variant?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Knapsack/subset sum problems share these signals: you’re selecting from a set of items (or numbers) to achieve a target, each item can be used a limited number of times, and you’re optimizing or counting. “Partition array into equal sums” u2192 subset sum (target = total/2). “Minimum coins to make amount” u2192 unbounded knapsack (minimize count). “Number of ways to make change” u2192 unbounded knapsack (count combinations). “Assign +/- to reach target” u2192 subset sum (convert to: find subset summing to (total+target)/2). “At most K of each item” u2192 bounded knapsack. The boolean dp (can we achieve X?) uses OR updates; the count dp uses sum updates; the optimization dp uses min/max updates.”
}
},
{
“@type”: “Question”,
“name”: “What is the time and space complexity of the knapsack DP, and how can space be optimized?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The naive 2D knapsack has O(n u00d7 W) time and O(n u00d7 W) space, where n is the number of items and W is the capacity. Space is optimized to O(W) by observing that dp[i][w] only depends on the previous row dp[i-1]. Using a 1D array and iterating items in the outer loop, with weights in reverse (for 0/1) or forward (unbounded) in the inner loop, achieves the same result with O(W) space. Time remains O(n u00d7 W). For subset sum problems (boolean values), a Python bitset optimization uses bitwise OR: “dp |= dp << num" which processes all capacity values simultaneously using machine-word parallelism, giving O(n u00d7 W/64) effective time."
}
}
]
}