The 0/1 Knapsack Pattern
The 0/1 Knapsack problem is one of the most important DP patterns — its structure appears in dozens of interview problems. Given items with weights and values, and a bag with capacity W, maximize the total value without exceeding weight W. Each item is either included (1) or excluded (0) — it cannot be split or used twice.
def knapsack_01(weights: list[int], values: list[int],
capacity: int) -> int:
n = len(weights)
# dp[i][w] = max value using first i items with capacity w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w_i = weights[i - 1]
v_i = values[i - 1]
for w in range(capacity + 1):
# Option 1: don't take 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][capacity]
# Space optimization: since dp[i] only depends on dp[i-1],
# use a 1D array and iterate w from RIGHT to LEFT
def knapsack_01_1d(weights: list[int], values: list[int],
capacity: int) -> int:
dp = [0] * (capacity + 1)
for w_i, v_i in zip(weights, values):
# Right to left: prevents using the same item twice
for w in range(capacity, w_i - 1, -1):
dp[w] = max(dp[w], dp[w - w_i] + v_i)
return dp[capacity]
Why right to left? If we iterated left to right, dp[w - w_i] would already be updated with item i included — we’d count the same item twice (becoming unbounded knapsack). Right-to-left uses values from before item i was considered.
Unbounded Knapsack (Coin Change)
Each item can be used unlimited times. Iterate left to right in the 1D array.
def coin_change(coins: list[int], amount: int) -> int:
"""Minimum coins to make amount (LC 322)."""
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 0 coins needed for amount 0
for a in range(1, amount + 1):
for coin in coins:
if coin int:
"""Number of ways to make amount (LC 518)."""
dp = [0] * (amount + 1)
dp[0] = 1 # One way to make 0: use no coins
for coin in coins:
for a in range(coin, amount + 1): # Left to right: unbounded
dp[a] += dp[a - coin]
return dp[amount]
Note the loop order difference: Coin Change iterates amount in the outer loop, coins in inner — same result. Coin Change Ways iterates coins in outer loop to avoid counting permutations as separate combinations (order matters / doesn’t matter).
Partition Equal Subset Sum (LC 416)
Classic 0/1 knapsack disguise: can we partition the array into two subsets with equal sum?
def can_partition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False # Odd total can't be split equally
target = total // 2
# dp[s] = True if we can form sum s using a subset of nums
dp = [False] * (target + 1)
dp[0] = True # Empty subset sums to 0
for num in nums:
# Right to left: 0/1 knapsack (use each num at most once)
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]
return dp[target]
# Generalization: Target Sum (LC 494) — assign + or - to each number,
# count ways to reach target. Reduce to subset sum:
def find_target_sum_ways(nums: list[int], target: int) -> int:
# Let P = sum of + subset, N = sum of - subset
# P - N = target, P + N = total → P = (total + target) / 2
total = sum(nums)
if (total + target) % 2 != 0 or abs(target) > total:
return 0
s = (total + target) // 2
# Count subsets with sum = s (unbounded-style counting with 0/1 constraint)
dp = [0] * (s + 1)
dp[0] = 1
for num in nums:
for i in range(s, num - 1, -1):
dp[i] += dp[i - num]
return dp[s]
Last Stone Weight II (LC 1049)
Find the minimum possible weight of the last remaining stone after smashing. This reduces to: partition stones into two groups S1 and S2, minimize |S1 – S2|. Equivalent to: find the largest subset sum S1 ≤ total/2.
def last_stone_weight_ii(stones: list[int]) -> int:
total = sum(stones)
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for stone in stones:
for s in range(target, stone - 1, -1):
dp[s] = dp[s] or dp[s - stone]
# Find largest achievable sum <= target
for s in range(target, -1, -1):
if dp[s]:
return total - 2 * s # |S1 - S2| = total - 2 * S1
return total
0/1 Knapsack vs Unbounded — Decision Guide
| Problem | Type | Iteration direction |
|---|---|---|
| 0/1 Knapsack, Partition Equal Subset | 0/1 (each item once) | Right to left |
| Coin Change (min coins), Coin Change II (ways) | Unbounded (repeat items) | Left to right |
| Target Sum, Last Stone Weight II | 0/1 (subset counting) | Right to left |
| Perfect Squares (LC 279) | Unbounded (reuse squares) | Left to right |
| Combination Sum IV (LC 377) | Unbounded + order matters | Left to right, coins outer |
Knapsack Template Recognition
A problem is a knapsack variant if:
- You have a set of items/numbers to choose from (each available once or unlimited times)
- There is a capacity/target constraint (max weight, exact sum, equal partition)
- You are maximizing value, minimizing cost, or counting ways to reach the target
Once recognized: define dp[w] = “best answer achievable with capacity/sum w”. Determine if items are used once (0/1 → right-to-left) or unlimited (unbounded → left-to-right). Initialize dp[0] appropriately (0 for min/count problems, True for existence problems). Fill dp[1..target].
🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
🏢 Asked at: Apple Interview Guide 2026: iOS Systems, Hardware-Software Integration, and iCloud Architecture
🏢 Asked at: Coinbase Interview Guide
🏢 Asked at: Atlassian Interview Guide
🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture