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].
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you recognize a knapsack pattern in coding interview problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A problem has knapsack structure if: (1) You have a collection of items to choose from. (2) There is a budget/capacity constraint (maximum weight, exact sum, target value). (3) Each item is used at most once (0/1 knapsack) or unlimited times (unbounded knapsack). (4) You want to maximize, minimize, or count configurations. Examples by disguise: “Can you partition this array into two equal subsets?” → 0/1 knapsack with target = total/2. “What is the minimum number of coins to make amount X?” → unbounded knapsack (each coin denomination can be used multiple times). “How many ways can you make change for N using these coins?” → unbounded counting knapsack. “Assign + or – to reach target sum” → 0/1 knapsack counting variant. “Largest subset with sum <= K" → 0/1 knapsack maximization. Template check: can you define dp[w] = "best result achievable with budget/sum exactly w or at most w"? If yes, it's knapsack. The recurrence is always: dp[w] = best(dp[w] without item_i, dp[w – weight_i] + value_i with item_i). The iteration direction determines 0/1 vs unbounded."}},{"@type":"Question","name":"Why does the 0/1 knapsack iterate the weight array from right to left?","acceptedAnswer":{"@type":"Answer","text":"In the space-optimized 1D DP array, we process each item once and update dp[w] in-place. The recurrence is dp[w] = max(dp[w], dp[w – w_i] + v_i). The key: when computing dp[w] for item i, dp[w – w_i] must reflect the state BEFORE item i was considered — i.e., the value achievable using items 1 through i-1 with capacity w – w_i. If we iterate left to right (w from 0 to W), then by the time we compute dp[w], dp[w – w_i] has already been updated with item i — it reflects "best with items 1..i and capacity w – w_i." This means item i could be included in dp[w – w_i] AND then included again in dp[w], effectively using item i twice. By iterating right to left (w from W down to w_i), when we compute dp[w], dp[w – w_i] has NOT yet been updated for item i — it still reflects "best with items 1..i-1 and capacity w – w_i." This ensures each item is used at most once. Unbounded knapsack WANTS to reuse items, so it iterates left to right deliberately, allowing dp[w – w_i] (already updated with item i) to reflect multiple uses of the same item."}},{"@type":"Question","name":"How do you solve Coin Change vs Coin Change II (ways) with DP?","acceptedAnswer":{"@type":"Answer","text":"Coin Change (LC 322) — minimum coins to reach amount: dp[a] = min coins to make amount a. Base: dp[0] = 0 (0 coins for 0 amount), dp[1..amount] = infinity. Recurrence: for each amount a, for each coin c <= a: dp[a] = min(dp[a], dp[a-c] + 1). Loop order: outer loop over amount (1 to amount), inner loop over coins. Return dp[amount] if finite, else -1. This is unbounded knapsack (can reuse coins). Coin Change II (LC 518) — number of ways to make amount: dp[a] = number of ways to make amount a. Base: dp[0] = 1 (one way: use no coins). Recurrence: for each coin c, for each amount a from c to amount: dp[a] += dp[a-c]. CRITICAL: outer loop must be over coins, inner loop over amount. If you swap the loops (outer=amount, inner=coins), you count permutations — [1,2] and [2,1] are counted separately, giving 4 ways for amount=3 instead of 2. The coin-outer order ensures each coin denomination is processed once, creating combinations without repetition of order. This is the same principle as "counting subsets": process each item (coin) once, updating forward — the coin is either used or not in each combination."}}]}
🏢 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