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.