The Knapsack DP Patterns

The "tell" that signals knapsack

Before the mechanics, the recognition. Knapsack problems are hiding in plain sight once you know what to look for.

The signal: you have a list of numbers (weights, values, integers, coin denominations). There's a target (capacity, sum, goal). You're asked whether you can reach the target exactly, maximize something within it, or count ways to hit it. Each element is considered independently — you either use it or you don't (or you use it as many times as you want).

That's it. If you read a problem and think "I'm picking from a pool to hit a number," pause and check if it's knapsack before reaching for anything else.

Real examples of the disguise:

• "Can you partition this array into two equal-sum subsets?" — subset sum in disguise (hit total/2).
• "Minimum number of coins to make amount X." — unbounded knapsack, different question on the same table.
• "How many ways to assign + or – to each number to reach target T?" — 0/1 knapsack over signed choices.
• "Word break: can you tile a string with dictionary words?" — unbounded knapsack over positions.

The base case: 0/1 knapsack

Items have weights and values. You have a knapsack of capacity W. Each item can go in at most once. Maximize total value.

State definition

dp[i][c] = maximum value achievable considering items 0..i with remaining capacity c.

That two-coordinate state — which items have I considered × how much capacity remains — is the fingerprint of this whole family.

The recurrence: take or skip

At item i with capacity c, you have exactly two choices:

1. Skip item i: dp[i][c] = dp[i-1][c] — inherit the best from previous items, capacity unchanged.
2. Take item i (only if weights[i] <= c): dp[i][c] = values[i] + dp[i-1][c - weights[i]] — add the value, reduce capacity, look at the rest without item i.

Take the better of the two:

dp[i][c] = max(dp[i-1][c], values[i] + dp[i-1][c - weights[i]])

The table fills left-to-right, top-to-bottom. Each cell only needs the row above it.

block-beta
  columns 6
  cap["capacity →"]:1 c0["c=0"]:1 c1["c=1"]:1 c2["c=2"]:1 c3["c=3"]:1 c4["c=4"]:1
  i0["no items"]:1 d00["0"]:1 d01["0"]:1 d02["0"]:1 d03["0"]:1 d04["0"]:1
  i1["item0\nw=2,v=3"]:1 d10["0"]:1 d11["0"]:1 d12["3"]:1 d13["3"]:1 d14["3"]:1
  i2["item1\nw=3,v=4"]:1 d20["0"]:1 d21["0"]:1 d22["3"]:1 d23["4"]:1 d24["4"]:1
  i3["item2\nw=4,v=5"]:1 d30["0"]:1 d31["0"]:1 d32["3"]:1 d33["4"]:1 d34["5"]:1

  style d12 fill:#7c5cff,color:#fff
  style d23 fill:#7c5cff,color:#fff
  style d34 fill:#7c5cff,color:#fff
  style d24 fill:#22d3ee,color:#0a0a0f

Reading the table: with capacity 4, item0 (w=2,v=3) fills at c=2. Item1 (w=3,v=4) fits at c=3 and scores 4, beating item0's 3. Item2 (w=4,v=5) fits exactly at c=4 with value 5 — but note it doesn't beat taking both item0 and item1 if W were larger. Follow the "take vs. skip" comparison cell by cell and the table builds itself.

The 2D implementation

def knapsack_01(weights, values, W):
    n = len(weights)
    # dp[i][c]: best value using items 0..i-1 with capacity c
    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):
            # skip item i
            dp[i][c] = dp[i - 1][c]
            # take item i (only if it fits)
            if w <= c:
                dp[i][c] = max(dp[i][c], v + dp[i - 1][c - w])

    return dp[n][W]

Time: O(n × W). Space: O(n × W). But you can do much better on space.

The 1D optimization — and WHY it works

Every cell in row i only looks at row i-1. So compress: use a single array and overwrite it. The trick is direction.

Iterate capacity right-to-left.

def knapsack_01_1d(weights, values, W):
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        w, v = weights[i], values[i]
        # RIGHT TO LEFT — critical
        for c in range(W, w - 1, -1):
            dp[c] = max(dp[c], v + dp[c - w])

    return dp[W]

Why right-to-left? When you update dp[c], the value dp[c - w] must still reflect the previous item's row — otherwise you're double-counting item i. Since c - w < c, iterating right-to-left means when you reach index c, the value at c - w hasn't been touched yet in this pass. It's still "last row." Going left-to-right would overwrite dp[c - w] first, letting you "use" item i again — which is the unbounded variant, not 0/1.

This is one of those things where getting the direction wrong produces subtly wrong answers that pass most small test cases. Burn the reason into memory, not just the direction.

Unbounded knapsack: items you can reuse

Same setup, but each item has no usage limit. Coin denominations are the classic: you can use as many 5-cent coins as you want.

The recurrence changes only slightly:

dp[i][c] = max(dp[i-1][c], values[i] + dp[i][c - weights[i]])
                                              ^ same row, not i-1

Taking item i leaves you free to take item i again. In 2D terms, "take" looks at the same row. In 1D terms:

Iterate capacity left-to-right.

def knapsack_unbounded(weights, values, W):
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        w, v = weights[i], values[i]
        # LEFT TO RIGHT — critical
        for c in range(w, W + 1):
            dp[c] = max(dp[c], v + dp[c - w])

    return dp[W]

Left-to-right means when you compute dp[c], dp[c - w] has already been updated in this pass — possibly using item i multiple times. That's exactly the behavior you want.

flowchart LR
    subgraph "0/1 — iterate RIGHT to LEFT"
      direction LR
      R1["dp[W]"] --> R2["dp[W-1]"] --> R3["..."] --> R4["dp[w]"]
      note1["dp[c-w] is still last-row\n→ no double-count"]
    end
    subgraph "Unbounded — iterate LEFT to RIGHT"
      direction LR
      L1["dp[w]"] --> L2["dp[w+1]"] --> L3["..."] --> L4["dp[W]"]
      note2["dp[c-w] already updated\n→ reuse allowed"]
    end
    style R1 fill:#7c5cff,color:#fff
    style L4 fill:#22d3ee,color:#0a0a0f

That one directional difference is the entire mechanical difference between the two variants. Everything else is the same template.

The disguises

Subset sum

Can you pick a subset of nums that sums to exactly T?

Knapsack where weight[i] = value[i] = nums[i], capacity = T, answer is boolean: dp[T] > 0 or dp[T] == T. More idiomatically, use dp[c] as a boolean:

def can_sum(nums, T):
    dp = [False] * (T + 1)
    dp[0] = True          # empty subset sums to 0

    for num in nums:
        for c in range(T, num - 1, -1):   # 0/1: right-to-left
            dp[c] = dp[c] or dp[c - num]

    return dp[T]

dp[c] = True means "some subset of the items seen so far sums to c." dp[0] = True is the base case: the empty subset achieves sum 0. Walk right-to-left for 0/1 (each number used at most once).

Partition equal subset sum (Leetcode 416)

Given an array, can you split it into two subsets with equal sums?

The total must be even. Then you need one subset summing to total // 2. That's subset sum with target total // 2. Exact same code, different target.

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

One insight unlocks the whole thing: you don't need to find both subsets. If one subset hits total/2, the rest automatically hits total/2 too.

Coin change — minimum coins (Leetcode 322)

Given coin denominations and an amount, return the minimum number of coins to make the amount. Coins are unlimited.

Unbounded knapsack. But the question is "minimum coins" not "maximum value," so initialize dp to infinity (except dp[0] = 0):

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0   # 0 coins to make amount 0

    for coin in coins:
        for c in range(coin, amount + 1):   # unbounded: left-to-right
            if dp[c - coin] != float('inf'):
                dp[c] = min(dp[c], 1 + dp[c - coin])

    return dp[amount] if dp[amount] != float('inf') else -1

The recurrence: to make amount c using this coin, it costs 1 coin plus whatever it costs to make c - coin. Minimize. Left-to-right because coins are reusable.

Coin change II — count ways (Leetcode 518)

Count distinct combinations of coins that sum to amount.

Still unbounded, but dp[c] is a count now and the recurrence adds instead of taking min:

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1   # one way to make 0: use no coins

    for coin in coins:
        for c in range(coin, amount + 1):
            dp[c] += dp[c - coin]

    return dp[amount]

Note the loop order: outer loop over coins, inner over amounts. This counts combinations (order doesn't matter: [1,2] and [2,1] are the same). If you swapped the loops — outer over amounts, inner over coins — you'd count permutations. The outer-coin loop ensures each coin denomination is "introduced" one at a time, so you never count the same combination in different orders.

Target sum (Leetcode 494)

Assign + or – to each element; count ways to reach target T.

This one is subtler. Let P be the sum of numbers assigned +, N the sum of numbers assigned –. Then P + N = total and P - N = T. Solve: P = (total + T) / 2. Now count subsets summing to P — 0/1 knapsack, count ways:

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (total + target) % 2 != 0 or abs(target) > total:
        return 0
    s = (total + target) // 2

    dp = [0] * (s + 1)
    dp[0] = 1

    for num in nums:
        for c in range(s, num - 1, -1):   # 0/1: right-to-left
            dp[c] += dp[c - num]

    return dp[s]

Reducing "assign signs" to "count subsets hitting a derived target" is a common algebraic trick. Once you see it once, you spot it fast.

Worked problem: partition equal subset

Let's trace through nums = [1, 5, 11, 5]. Total = 22, target = 11.

block-beta
  columns 13
  cap["c→"]:1 c0["0"]:1 c1["1"]:1 c2["2"]:1 c3["3"]:1 c4["4"]:1 c5["5"]:1 c6["6"]:1 c7["7"]:1 c8["8"]:1 c9["9"]:1 c10["10"]:1 c11["11"]:1
  base["init"]:1 b0["T"]:1 b1["F"]:1 b2["F"]:1 b3["F"]:1 b4["F"]:1 b5["F"]:1 b6["F"]:1 b7["F"]:1 b8["F"]:1 b9["F"]:1 b10["F"]:1 b11["F"]:1
  r1["num=1"]:1 r10["T"]:1 r11["T"]:1 r12["F"]:1 r13["F"]:1 r14["F"]:1 r15["F"]:1 r16["F"]:1 r17["F"]:1 r18["F"]:1 r19["F"]:1 r110["F"]:1 r111["F"]:1
  r2["num=5"]:1 r20["T"]:1 r21["T"]:1 r22["F"]:1 r23["F"]:1 r24["F"]:1 r25["T"]:1 r26["T"]:1 r27["F"]:1 r28["F"]:1 r29["F"]:1 r210["F"]:1 r211["F"]:1
  r3["num=11"]:1 r30["T"]:1 r31["T"]:1 r32["F"]:1 r33["F"]:1 r34["F"]:1 r35["T"]:1 r36["T"]:1 r37["F"]:1 r38["F"]:1 r39["F"]:1 r310["F"]:1 r311["T"]:1
  r4["num=5"]:1 r40["T"]:1 r41["T"]:1 r42["F"]:1 r43["F"]:1 r44["F"]:1 r45["T"]:1 r46["T"]:1 r47["F"]:1 r48["F"]:1 r49["F"]:1 r410["T"]:1 r411["T"]:1

  style b0 fill:#00ff9d,color:#0a0a0f
  style r311 fill:#7c5cff,color:#fff
  style r411 fill:#7c5cff,color:#fff

After processing num=11, dp[11] flips to True (you can hit 11 by picking just {11}). After processing the second num=5, dp[10] also flips (5+5=10) and dp[11] stays True. Answer: True — the partition is {11} and {1,5,5}.

Pitfalls people actually hit

Wrong loop direction. This is the #1 source of subtle wrong answers. Getting right-to-left and left-to-right confused produces solutions that pass small test cases (where numbers don't repeat the index) and fail large ones. Practice writing the direction comment explicitly every time.

Forgetting dp[0] = True/1. The base case isn't "zero items" — it's "zero capacity can always be achieved by taking nothing." If you initialize the whole array to False/0 without setting dp[0], your recurrence has nothing to propagate from and you'll return False for all inputs.

Using dp[amount] = -1 for "not possible" and then subtracting from it. In coin change, initialize to float('inf'), not -1. Subtracting from -1 creates garbage values that quietly propagate through the min operations.

Confusing combinations and permutations in count-ways problems. Outer loop over items gives combinations (each item "introduced" once). Outer loop over capacity gives permutations. Most problems want combinations. Coin Change II explicitly says "number of combinations" — that's the outer-items order. If you get 4 instead of 5 or 5 instead of 4, check your loop order.

Not checking divisibility before subset sum. In partition equal subset and target sum, invalid inputs (total % 2 != 0, abs(target) > total) should short-circuit early. Failing to check means you'll index a negative target and either crash or produce nonsense.

Treating zeros in the input carelessly. A coin or weight of 0 makes inner loops infinite or no-ops depending on how you wrote them. Guard against it explicitly in production code, even if LeetCode inputs don't include zeros.

When NOT to use knapsack DP

Knapsack has O(n × W) complexity. That's fine when both n and W are in the thousands. But it breaks down in a few real scenarios:

• W is huge. If weights/values are integers up to 10⁹, the DP table is 10⁹ wide. You can't allocate that. Look for a meet-in-the-middle approach (split items in half, enumerate all subset sums for each half, binary search for complements) — O(2^(n/2)), which beats DP when W is astronomical.
• Items aren't independent. If taking item A forces you to also take item B (dependencies, "group knapsack"), the recurrence needs a different state structure or a tree DP layer.
• You need to list the items in the optimal solution, not just the value. The 1D optimization destroys the reconstruction path. Either keep the full 2D table (and backtrack from dp[n][W]) or annotate which items were taken as you fill.
• Greedy is sufficient. Fractional knapsack (you can take fractions of items) is solved optimally by greedy: sort by value/weight ratio, take the best ratio until full. No DP needed. If the problem says fractions are allowed, don't reach for DP.

The deeper issue: if you find yourself forcing a problem into knapsack because you don't see another angle, pause. Knapsack requires independent, discrete choices with a numeric capacity constraint. If your "items" have side effects on each other, or the "capacity" isn't additive, a different DP formulation will serve you better. See dp on grids for a related family where the state isn't an item index at all, and dynamic programming for the broader taxonomy.

The template to internalize

# 0/1 KNAPSACK — each item at most once
def knapsack_01_template(items, W, ask="max"):
    # items: list of (weight, value) tuples
    # W: capacity
    # ask: "max" → maximize value; "bool" → can we hit exactly W?; "count" → ways to hit W
    
    if ask == "bool":
        dp = [False] * (W + 1); dp[0] = True
        for w, v in items:
            for c in range(W, w - 1, -1):
                dp[c] = dp[c] or dp[c - w]
        return dp[W]
    
    if ask == "count":
        dp = [0] * (W + 1); dp[0] = 1
        for w, v in items:
            for c in range(W, w - 1, -1):
                dp[c] += dp[c - w]
        return dp[W]
    
    # ask == "max" (default)
    dp = [0] * (W + 1)
    for w, v in items:
        for c in range(W, w - 1, -1):
            dp[c] = max(dp[c], v + dp[c - w])
    return dp[W]


# UNBOUNDED KNAPSACK — items reusable
def knapsack_unbounded_template(items, W, ask="max"):
    if ask == "min":
        dp = [float('inf')] * (W + 1); dp[0] = 0
        for w, v in items:
            for c in range(w, W + 1):
                if dp[c - w] != float('inf'):
                    dp[c] = min(dp[c], v + dp[c - w])
        return dp[W] if dp[W] != float('inf') else -1
    
    if ask == "count":
        dp = [0] * (W + 1); dp[0] = 1
        for w, v in items:
            for c in range(w, W + 1):
                dp[c] += dp[c - w]
        return dp[W]
    
    # ask == "max"
    dp = [0] * (W + 1)
    for w, v in items:
        for c in range(w, W + 1):
            dp[c] = max(dp[c], v + dp[c - w])
    return dp[W]

The only four things that change between variants: (1) 0/1 vs. unbounded → iteration direction; (2) maximize, minimize, boolean, or count → how you combine dp[c] with dp[c - w]; (3) initial value of dp[0]; (4) initial value of all other cells.

Everything else — the outer loop over items, the inner loop over capacity, the conditional on c >= w — stays identical.

---

If this is your first time reading about knapsack, go implement coin change (Leetcode 322) and partition equal subset (Leetcode 416) back-to-back. The muscle memory of writing the loop direction correctly twice in a row does more than rereading this article three times. Then try target sum (Leetcode 494) for the algebraic reduction trick. Those three problems cover the whole family.

For the broader DP landscape, dynamic programming has the full framework for identifying DP problems and defining states. For the 2D cousin of this pattern — where your state is a grid position rather than an index+capacity — see dp on grids. And if any of these problems arrive during a system design that involves scheduling or prioritization, heaps often pair with DP to efficiently track the current best candidate.