L37 · DP V — 0/1 Knapsack

Series: LeetCode — From Basics to Interview-Ready · Session 37 / 65 · Phase 2 · Dynamic programming

Prerequisites

L33–L35 (state definition, recurrence, memo→table). You should be able to write take/skip 1D DP without notes. 0/1 knapsack is take/skip with a second axis — the remaining budget — so if L35 is shaky, do it first.

Watch first (skim before the session)

Why this session exists

0/1 knapsack is the most frequently disguised DP in interviews. The naked version — "items with weights and values, a capacity W, maximise value, each item at most once" — is rarely asked directly. Instead you get: can this array be split into two equal-sum halves? (Partition Equal Subset Sum), how many ways to reach target T with +/- signs? (Target Sum), smallest difference between two piles? (Last Stone Weight II). Every one is a boolean or counting 0/1 knapsack.

The reason it is worth a whole session is the at-most-once constraint, which forces one specific detail in the space-optimised version: you iterate the capacity axis backwards. Getting that direction wrong silently converts 0/1 knapsack into unbounded knapsack (L38) — the code runs, the answer is wrong, and it is the single most common knapsack bug in interviews.

Blank-file warm-up

Five minutes, empty file, no notes. Write the 1D roll from memory:

for each item (w, v):
    for cap from W down to w:          # BACKWARDS — this is the whole game
        dp[cap] = max(dp[cap], dp[cap - w] + v)

If the loop direction wobbles, you do not know this session yet. Backwards = each item used at most once. Forwards = unbounded (L38).

From first principles

The 2D table, easiest to reason about:

def knapsack_2d(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]                     # skip item i-1
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)   # take it
    return dp[n][W]
 
assert knapsack_2d([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9   # items (3,4)+(4,5) -> weight 7, value 9

The space-optimised 1D version — what you should actually write in an interview:

def knapsack_1d(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(W, w - 1, -1):        # HIGH -> LOW: at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[W]
 
assert knapsack_1d([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9

Mental model

Memory hook

"One of each, sweep the budget backwards." The phrase binds the constraint (one of each item) to the fix (backwards capacity loop). Its sibling in L38 is "unlimited, sweep forwards." Learn them as a matched pair and you will never flip the direction under pressure.

What interviewers actually ask

Almost never the naked backpack. Here are the real disguises, with what is being probed.

• LC416 · Partition Equal Subset Sum — Amazon, Meta. Reduce to: is there a subset summing to total/2? Boolean 0/1 knapsack with capacity = sum/2. Probe: do you spot that odd total ⇒ instant False, and that this is subset-sum, not a fresh DP? Follow-up: what if you needed the actual subset?
• LC494 · Target Sum — Amazon, Meta. Assign +/- to each number to hit target T. Algebra: elements assigned + form a subset summing to (T + total)/2, so it's counting 0/1 knapsack (dp[c] += dp[c-w]). Probe: the reduction, and the parity/bounds check that makes (T+total) even and non-negative.
• LC1049 · Last Stone Weight II — Amazon. Minimise the final stone = split into two piles with minimal difference = find the subset summing closest to total/2. Probe: recognising "minimal difference of two piles" as subset-sum.
• LC474 · Ones and Zeroes — Google. A two-budget 0/1 knapsack (m zeros and n ones as twin capacities). Probe: can you carry TWO capacity axes and still keep both loops backwards?
• LC698 · Partition to K Equal Sum Subsets — Amazon (Hard). Generalisation; usually needs bitmask/backtracking, but candidates who know subset-sum reason about it faster. Probe: why the simple knapsack doesn't directly extend to k parts.
• LC322 · Coin Change — Amazon, Google. This is the UNBOUNDED cousin (L38) — included here so you feel the contrast: same table shape, forward loop, coins reusable.

Escalation ladder: naked knapsack → boolean subset-sum → counting subset-sum → two-budget → k-partition. Interviewers climb this exact staircase.

A worked reduction: Partition Equal Subset Sum

Brute force: try all 2ⁿ subsets, check if any sums to total/2 — exponential. The insight: this is exactly "can I fill a backpack of capacity total/2 exactly?", a boolean 0/1 knapsack.

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:                        # odd total can't split evenly
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True                         # sum 0 is always reachable (empty subset)
    for x in nums:
        for c in range(target, x - 1, -1):   # backwards: each number once
            dp[c] = dp[c] or dp[c - x]
    return dp[target]
 
assert can_partition([1, 5, 11, 5]) is True     # [1,5,5] and [11]
assert can_partition([1, 2, 3, 5]) is False

• Complexity: O(n · target) time, O(target) space.
• Follow-up they escalate to: return the actual subset (keep parent pointers), or handle very large sums (then the pseudo-polynomial DP is too big and you discuss why no truly polynomial solution is known — subset-sum is NP-complete).

Tradeoff

In practice

Knapsack-style DP is how resource schedulers and budget allocators reason: given a fixed compute/memory budget and a set of jobs each with a cost and a benefit, pick the subset that maximises benefit. It's also the backbone of "cut optimally" problems in build systems and the classic subset-sum core inside cryptographic knapsack schemes (now broken, but historically real). The pseudo-polynomial nature — fast only when the budget is small — is exactly why these tools cap the budget dimension.

Practice queue

Solve in this order; log each as cold / warm / hint / failed.

1. LC416 Partition Equal Subset Sum — boolean subset-sum, the gateway.
2. LC494 Target Sum — counting subset-sum.
3. LC1049 Last Stone Weight II — minimal-difference subset-sum.
4. LC474 Ones and Zeroes — two-budget knapsack.
5. LC698 Partition to K Equal Sum Subsets — where knapsack meets bitmask/backtracking.