04 — Knapsack Patterns

Phase 4 | Week 26–27 | Feb 2 – Feb 8, 2027

The knapsack family is the most misunderstood cluster in DP. People solve Coin Change and Subset Sum as if they’re unrelated problems, then wonder why they keep getting them wrong. They’re the same problem with minor structural variations. Once you see the template, you can derive any knapsack variant in under two minutes. The key insight: the inner loop direction controls whether items can be reused, and almost nobody knows why.

The Knapsack Template

Every knapsack variant has this skeleton:

dp[j] = "best answer using capacity/sum j"
for each item:
    for j in [some range]:
        dp[j] = combine(dp[j], dp[j - item_weight] + item_value)

What changes between variants:

  1. Whether items can be reused (inner loop direction)

  2. Whether we want a count, a boolean, or a max/min value

  3. Whether there are quantity limits on items

1. 0/1 Knapsack — Each Item Used At Most Once

Problem: N items, each with weight w[i] and value v[i]. Knapsack capacity W. Maximize total value without exceeding capacity. Each item is either taken (1) or not (0).

State: dp[j] = maximum value achievable with exactly capacity j (or at most j).

2D formulation (easier to reason about):

dp[i][j] = max value using items 0..i-1 with capacity j

dp[i][j] = max(
    dp[i-1][j],              # don't take item i
    dp[i-1][j-w[i]] + v[i]  # take item i (only if j >= w[i])
)

Space-optimized (1D): Compress the first dimension. Since dp[i] only depends on dp[i-1], use a single array — BUT iterate j from right to left (W down to w[i]).

dp = [0] * (W + 1)
for i in range(N):
    for j in range(W, w[i]-1, -1):   # RIGHT TO LEFT
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

Why right to left? When you compute dp[j], you need dp[j - w[i]] from the previous item iteration. If you iterate left to right, you’d overwrite dp[j - w[i]] before using it, which would allow item i to be used multiple times — turning it into unbounded knapsack.

2. Unbounded Knapsack — Each Item Used Unlimited Times

Problem: Same setup, but each item can be chosen any number of times.

State: Same as 0/1 knapsack.

1D formulation: Iterate j from left to right (w[i] to W).

dp = [0] * (W + 1)
for i in range(N):
    for j in range(w[i], W + 1):    # LEFT TO RIGHT
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

Why left to right? When computing dp[j], you want to allow item i to be used again. If dp[j - w[i]] has already been updated in this iteration (because j - w[i] < j and we go left to right), it reflects “already used item i once,” and adding item i again is valid.

This is the only difference between 0/1 and unbounded. One loop direction. Understand why, don’t memorize which.

Coin Change is unbounded knapsack with v[i] = 1 for all coins, minimizing instead of maximizing. The loop structure is identical — left to right inner loop.

3. Bounded Knapsack — Each Item Has a Limit

Problem: Item i can be used at most c[i] times.

Naive approach: Expand each item into c[i] copies and run 0/1 knapsack. Works, but slow if counts are large.

Binary grouping optimization: Split item with count c into groups of 1, 2, 4, …, remainder. Each group is treated as a single item in 0/1 knapsack. This reduces O(c) items to O(log c) items.

This shows up occasionally in competitive programming but rarely in FAANG interviews. Know it exists; implement it if asked.

4. Subset Sum — Can We Make Exactly Sum S?

Problem: Given an array of non-negative integers, can some subset sum to exactly S?

This is 0/1 knapsack where:

  • Weight = value = number itself

  • Capacity = S

  • Goal is boolean (can we reach S?), not maximize

State: dp[j] = True if some subset sums to j.

Transition (0/1 — iterate right to left):

dp = [False] * (S + 1)
dp[0] = True
for num in nums:
    for j in range(S, num-1, -1):
        dp[j] = dp[j] or dp[j - num]

Answer: dp[S]

5. Partition Equal Subset Sum

Problem: Can we split the array into two subsets with equal sum?

Reduction: Total sum must be even. If it is, find if subset sums to total // 2. This is exactly Subset Sum with S = total / 2.

total = sum(nums)
if total % 2 != 0: return False
return subset_sum(nums, total // 2)

This is one of the most common medium DP problems on LeetCode. The reduction is the insight.

6. Target Sum — How Many Ways?

Problem: Given array nums and target T, assign + or - to each number. How many assignments reach target T?

Naive approach: 2^n bitmask enumeration. Too slow for n > 20.

Knapsack reduction: Let P = set of numbers with +, N = set with -.

  • P + N = total

  • P - N = T

  • Solving: P = (total + T) / 2

So: “how many subsets sum to (total + T) / 2?” — this is a counting knapsack variant.

State: dp[j] = number of subsets that sum to exactly j.

Transition (0/1, right to left — each number used once):

dp = [0] * (S + 1)
dp[0] = 1   # empty subset sums to 0 in 1 way
for num in nums:
    for j in range(S, num-1, -1):
        dp[j] += dp[j - num]

Answer: dp[S] where S = (total + T) / 2.

Note: If (total + T) is odd or T > total, return 0.

7. Coin Change II — Number of Ways (Unbounded Counting)

Problem: Given coin denominations and amount, how many distinct combinations sum to amount? (Unlimited coins.)

State: dp[j] = number of ways to make amount j.

This is unbounded counting knapsack — left to right inner loop:

dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
    for j in range(coin, amount + 1):   # LEFT TO RIGHT
        dp[j] += dp[j - coin]

Compare with Target Sum: Target Sum is 0/1 (each number once, right to left). Coin Change II is unbounded (each coin unlimited, left to right). Both count combinations. The loop direction is the only structural difference.

What Most Engineers Get Wrong

The inner loop direction is the #1 mistake in knapsack DP. Most people memorize “right to left for 0/1, left to right for unbounded” without understanding why. Then they freeze on a variant they haven’t seen before.

Why it works, mechanically:

  • Array dp represents the state after processing all items so far.

  • In 0/1: when updating dp[j], you must use dp[j - w[i]] as it was before processing item i (i.e., without item i). Right-to-left ensures you read the old value.

  • In unbounded: when updating dp[j], you want dp[j - w[i]] including item i (since you can reuse it). Left-to-right ensures you read the already-updated value from this iteration.

If this still feels abstract, trace through Coin Change with coins = [2] and amount = 4:

  • Left to right: dp[2] gets updated → dp[4] = dp[2] + … = multiple ways (correct: unlimited use)

  • Right to left: dp[4] would use dp[2] from before coin 2 was processed → counts 0 ways from coin 2 (wrong for unbounded)

Practice Problems

Easy

  1. Partition Equal Subset Sum — LeetCode 416. The reduction is the puzzle. Once you see it, it’s just subset sum.

  2. Target Sum — LeetCode 494. The algebraic reduction to subset sum. Two approaches: brute-force DFS (correct but slow), and DP counting.

  3. Can I Win — LeetCode 464. 0/1 knapsack variant with bitmask (n ≤ 20). Easier than it looks.

Medium

  1. Coin Change — LeetCode 322. Unbounded knapsack, minimize coins. Left to right inner loop.

  2. Coin Change II — LeetCode 518. Unbounded counting. Same loop, different combination semantics.

  3. Ones and Zeroes — LeetCode 474. 2D knapsack — capacity has two dimensions (count of 0s and 1s). State is dp[i][j].

  4. Last Stone Weight II — LeetCode 1049. Reduce to partition equal subset sum. The “minimize difference” framing disguises it.

Hard

  1. Freedom Trail — LeetCode 514. Knapsack variant on a circular string. State design requires ring position + string position.