DP — knapsack family
📖 Walk me through it — plain English
"Knapsack" is the classic puzzle: you have a backpack that holds only so much weight (the capacity), a pile of items each with a weight, and you must decide which items to take. This whole lesson is about one shape of problem: pick a selection of numbers under a budget. The questions vary — can a subset hit an exact total? what is the fewest coins to make an amount? how many ways are there? — but they are all solved by the same little loop.
The tool is a 1-D array we call dp. The index is "how much capacity (or target) I am trying to fill," and the value at that index answers a question about exactly that amount. For Subset Sum, dp[c] is a true/false flag meaning "can some subset of the numbers I have seen so far add up to exactly c?" We seed dp[0] = True because the empty selection (taking nothing) always sums to 0. Then we feed in one number at a time and update the flags.
The one fork in the whole family is the direction of the inner loop over capacity. Sweeping capacity from high down to low means each item can be used at most once (that is "0/1"). Sweeping low up to high lets an item be reused freely (that is "unbounded," like coins). Everything else — bool vs min vs count — is just which arithmetic you fold in.
Analogy: imagine a row of mailboxes numbered 0, 1, 2, 3, 4, each either lit (reachable) or dark. Mailbox 0 starts lit. Each new number you are handed lets you light box c if box c minus that number was already lit — you "jump forward" by the number's size. Sweeping high-to-low guarantees you only ever jump from a box that was lit before this number arrived, so you can't use the same number twice in one round.
Let's trace subset_sum([1, 3], target = 4) — "can some subset of {1, 3} sum to 4?" The boxes are indices 0..4. Lit = green (reachable), dark = grey. The box being written this step is outlined in the accent color.
Why the high-to-low direction matters: when we wrote dp[4] using dp[1], the value at dp[1] came from the previous item's round (the 1), not from this round's processing of the 3 — this round only touches boxes 4 and 3, never box 1. So each number is folded in at most once — that is the meaning of 0/1. If we had instead swept low-to-high for an unbounded problem like coins, by the time we reach dp[4] the box we read may already include the current coin from earlier in this same sweep, letting the coin stack — exactly what you want when coins are reusable.
Why it is fast: there are n items, and for each we sweep up to C capacity slots, so the work is n × C simple updates — time O(n · C). We only ever keep one row of length C + 1, so space is O(C). One caution: this counts as "pseudo-polynomial" because it grows with the numeric size of C (the budget value), not with how many digits C has — a huge target makes the array huge.
Knapsack is the archetype for "pick items under a budget." You walk a list of items and a 1-D array dp indexed by remaining capacity; dp[c] answers "best (or count, or reachable) using capacity exactly c." Process one item at a time, folding it into dp. The whole family — subset-sum, partition, coin change, target sum — is this one loop. The single structural fork is the direction of the inner capacity loop: 0/1 (each item usable once) sweeps capacity high to low so the item can't fold into itself within one pass; unbounded (items reusable) sweeps low to high so it can. Anchor it on coins: with infinite coins you reuse a coin freely (low to high); with a bag of distinct objects you spend each at most once (high to low).
- "Choose items under a budget / weight capacity"
- "Is there a subset summing to a target?"
- "Split the array into two equal-sum halves"
- "Fewest coins / items to reach a total"
- "Count the number of ways to make a total"
- Each choice is binary (take / skip) and capacity is a small integer
- Subset Sum — 0/1, reachability (bool)
- Partition Equal Subset Sum — subset-sum to total/2
- Coin Change — unbounded, min coins for amount
- Coin Change II — unbounded, count combinations
- Target Sum — assign +/-, reduces to a 0/1 count
# ---- 0/1 knapsack: each item used AT MOST once ----
# Subset Sum: can any subset of nums hit target?
def subset_sum(nums, target):
dp = [False] * (target + 1)
dp[0] = True # empty subset makes 0
for x in nums:
for c in range(target, x - 1, -1): # HIGH -> LOW: no reuse of x
dp[c] = dp[c] or dp[c - x]
return dp[target]
# Partition Equal Subset Sum = subset_sum(nums, total // 2)
def can_partition(nums):
s = sum(nums)
if s % 2: return False # odd total can't split evenly
return subset_sum(nums, s // 2)
# ---- Unbounded knapsack: each item reusable ----
# Coin Change: fewest coins to make amount (-1 if impossible)
def coin_change(coins, amount):
INF = float('inf')
dp = [INF] * (amount + 1)
dp[0] = 0
for coin in coins:
for c in range(coin, amount + 1): # LOW -> HIGH: coin reusable
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != INF else -1
# Coin Change II: COUNT combinations making amount
def coin_change_2(coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make 0: take nothing
for coin in coins: # coins OUTER => combinations
for c in range(coin, amount + 1): # LOW -> HIGH: reusable
dp[c] += dp[c - coin]
return dp[amount]
# Target Sum: +/- each num to reach t. P - N = t, P + N = sum
# => P = (sum + t)/2, then COUNT 0/1 subsets summing to P
def target_sum(nums, t):
s = sum(nums)
if (s + t) % 2 or abs(t) > s: return 0
P = (s + t) // 2
dp = [0] * (P + 1)
dp[0] = 1
for x in nums:
for c in range(P, x - 1, -1): # HIGH -> LOW: 0/1 count
dp[c] += dp[c - x]
return dp[P]// 0/1: capacity HIGH -> LOW so each item folds in once
function subsetSum(nums: number[], target: number): boolean {
const dp = new Array(target + 1).fill(false);
dp[0] = true;
for (const x of nums)
for (let c = target; c >= x; c--) // HIGH -> LOW
dp[c] = dp[c] || dp[c - x];
return dp[target];
}
// Unbounded count: coins OUTER, capacity LOW -> HIGH => combinations
function coinChange2(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1; // seed: 1 way to make 0
for (const coin of coins)
for (let c = coin; c <= amount; c++) // LOW -> HIGH
dp[c] += dp[c - coin];
return dp[amount];
}In a single 1-D array, dp[c - x] is read before dp[c] is written. Going high to low, dp[c - x] still holds the value from before this item's pass, so item x contributes at most once — that is 0/1. Going low to high, dp[c - x] may already include x from earlier this same pass, so x can stack — that is unbounded. Memorize this and you derive every variant on the spot.
- Time O(n · C), space O(C) with the 1-D array — n items, C = capacity/target. This is pseudo-polynomial: it scales with the numeric value C, not its bit-length.
- 0/1 reuse bug: if you sweep capacity low to high in a 0/1 problem, dp[c - x] already counted x this pass, silently reusing the item. High to low is mandatory.
- Counting ways needs dp[0] = 1: the empty selection is one valid way to make 0. Leaving it 0 makes every count collapse to 0.
- Reachability vs min vs count differ only in the fold: or (bool), min(…)+1 (fewest), += (count). The loops are identical.
- Combinations vs permutations (counting only): items OUTER, capacity inner counts combinations ({1,2} once). Capacity OUTER, items inner counts permutations ({1,2} and {2,1}) — that is Combination Sum IV.
- Capacity axis sizing is target + 1 (indices 0..target). The inner range starts at the item's weight (x or coin) so c - x >= 0 always.
- Reductions: Partition needs even total then subset-sum to total/2; Target Sum needs (sum + t) even and |t| <= sum, then a 0/1 count to (sum + t)/2.
Count coin combinations to a target — unbounded knapsack: