0/1 Knapsack / Subset Sum

Imagine a thief breaks into a store. They have a bag that can hold at most W kilograms. The store has n items, each with a weight and a value. The thief wants to maximize the total value they carry out, but they cannot exceed the bag's capacity, and each item is either taken whole or left behind, with no cutting items in half. This is the 0/1 knapsack problem, and it is one of the most important patterns in dynamic programming.

The "0/1" means each item gets a binary decision: include it (1) or exclude it (0). This distinguishes it from the fractional knapsack (solvable by greedy) and the unbounded knapsack (where you can take each item multiple times). The 0/1 constraint is what makes the problem require DP. Greedy does not work because taking a lighter, less valuable item might free up capacity for a combination that is collectively better.

The 2D formulation

The most intuitive way to think about the knapsack is with a 2D table. Define dp[i][j] as the maximum value achievable using only the first i items with a capacity of j. For each item, you have two choices: skip it, or take it (if it fits). The recurrence is:

dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])   if j >= w[i]
dp[i][j] = dp[i-1][j]                                     if j < w[i]

The first option (dp[i-1][j]) means "do not take item i, so the best value with capacity j is the same as it was with only the first i-1 items." The second option (dp[i-1][j - w[i]] + v[i]) means "take item i, using up w[i] capacity and gaining v[i] value, plus whatever was optimal for the remaining capacity using the first i-1 items."

Let us walk through a small example. Suppose capacity W = 7, and we have four items:

We build the table row by row. After processing all items, dp[4][7] = 9: taking items B (weight 3, value 4) and C (weight 4, value 5) fills exactly capacity 7 for a total value of 9.

The 2D table has size $O(n \cdot W)$, and filling each cell is $O(1)$, so the total time is $O(n \cdot W)$.

Compressing to 1D

Look at the recurrence again: dp[i][j] only depends on dp[i-1][j] and dp[i-1][j - w[i]], both from the previous row. We never look back more than one row. This means we can collapse the table into a single 1D array of size W+1, reusing it for each item.

But there is a subtlety that trips up nearly everyone the first time.

Why reverse iteration matters

When we collapse to 1D, the update becomes dp[j] = max(dp[j], dp[j - w] + v). The question is: in what order do we iterate over j?

Suppose we iterate forward, from j = w up to j = W. Consider an item with weight 2 and value 3. When we compute dp[4], we look at dp[4 - 2] = dp[2]. But we already updated dp[2] earlier in this same loop, so it now reflects taking this item. So dp[4] would effectively be "take this item at capacity 2, then take it again to reach capacity 4." We have used the item twice. Forward iteration turns the 0/1 knapsack into an unbounded knapsack.

Now suppose we iterate backward, from j = W down to j = w. When we compute dp[4], we look at dp[2], which has not been updated yet in this round, so it still holds the value from the previous item's iteration. So we are correctly reading from the "previous row" of the conceptual 2D table. Each item is used at most once.

This is the single most important detail in knapsack problems: backward iteration gives 0/1 (each item once), forward iteration gives unbounded (items reusable).

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for j in range(capacity, w - 1, -1):  # backward!
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

Subset sum: the boolean special case

Subset sum asks: given a set of positive integers, is there a subset that adds up to exactly target? This is the knapsack where every item's "value" equals its "weight," and instead of maximizing value, we just want to know if the target is reachable.

The DP array becomes boolean. dp[j] is True if some subset of the items seen so far sums to exactly j. The base case is dp[0] = True (the empty subset sums to 0). The update is:

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

Same structure, same backward iteration, just boolean OR instead of max. If dp[j - num] was reachable before this item, then dp[j] is reachable after including this item.

Partition equal subset sum: the disguise

The problem LeetCode 416 asks: can you partition an array into two subsets with equal sum? At first glance, this does not look like a knapsack problem. But think about it: if the total sum is S, you need one subset summing to S/2 (the other automatically sums to S/2 as well). If S is odd, it is impossible. If S is even, the problem reduces to: is there a subset summing to S/2?

That is exactly subset sum with target = sum(nums) // 2.

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

The hardest part of this problem is not the algorithm. It is recognizing that "partition into equal halves" is subset sum.

Target sum: another disguise

Take LeetCode 494: given an array of non-negative integers and a target, assign a + or - sign to each number so they sum to the target. How many ways can you do it?

Let P be the sum of numbers assigned + and N be the sum assigned -. We need P - N = target, and P + N = total. Adding these: 2P = target + total, so P = (target + total) / 2. If target + total is odd or negative, there are zero ways. Otherwise, count the number of subsets summing to P.

This is a counting variant of subset sum. The update changes from boolean OR to addition:

def findTargetSumWays(nums, target):
    total = sum(nums)
    if (target + total) % 2 != 0 or target + total < 0:
        return 0
    goal = (target + total) // 2
    dp = [0] * (goal + 1)
    dp[0] = 1
    for num in nums:
        for j in range(goal, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[goal]

Here dp[j] counts the number of subsets summing to j. The base case dp[0] = 1 means there is one way to sum to zero: choose nothing. The update dp[j] += dp[j - num] says: every way to reach j - num gives us a new way to reach j by including the current number.

0/1 vs. unbounded: forward vs. backward

It is worth being explicit about the difference, since many problems ask for the unbounded variant. In coin change, for example, you can reuse each coin as many times as you want. The only code change is the inner loop direction:

# 0/1 knapsack: each item used at most once
for num in nums:
    for j in range(target, num - 1, -1):  # backward
        dp[j] = max(dp[j], dp[j - num] + num)

# Unbounded knapsack: items reusable
for num in nums:
    for j in range(num, target + 1):       # forward
        dp[j] = max(dp[j], dp[j - num] + num)

Forward iteration allows an item to contribute multiple times within the same pass. Backward iteration prevents this. If you ever forget which direction to use, trace through a small example with one item and see whether it gets used once or multiple times.

Counting variants

The counting pattern dp[j] += dp[j - num] shows up frequently. Besides target sum, it applies to:

• Coin change II (number of ways to make change): unbounded, so forward iteration with dp[j] += dp[j - coin].
• Number of subsets that sum to k: 0/1, so backward iteration with dp[j] += dp[j - num].
• Last stone weight II: minimize the final stone weight, which reduces to finding the subset sum closest to total/2, a variant of the optimization knapsack.

The pattern is always the same table and the same iteration; what changes is the operator (max, boolean OR, addition) and the direction (forward or backward).

Complexity analysis

Time: $O(n \cdot target)$ where n is the number of items and target is the capacity or sum limit. This is pseudo-polynomial: polynomial in the numeric value of the target, not in the number of bits needed to represent it. For large targets, this can be slow, which is why some subset sum problems with very large sums require meet-in-the-middle or other techniques instead.

Space: $O(target)$ with the 1D optimization. The 2D version uses $O(n \cdot target)$, but since each row only depends on the previous row, the 1D compression is almost always preferred.

Recognizing this pattern

You're probably looking at 0/1 knapsack when:

• You have a fixed collection of items and an independent take-or-leave decision for each one.
• There's a capacity, target sum, or budget that the chosen items must respect.
• The problem asks you to maximize value, hit a target exactly, count subsets, or partition into balanced groups.
• The numeric target is bounded ($\le 10^4$ or so), large enough to forbid $2^n$ brute force, small enough that $O(n \cdot \text{target})$ fits.

Common templates:

• Boolean subset sum: dp[j] |= dp[j - num], iterate j backward. Example: Partition Equal Subset Sum.
• Counting subsets: dp[j] += dp[j - num] to count ways to hit each sum. Example: Target Sum.
• Max-value knapsack: dp[j] = max(dp[j], dp[j - w] + v), the classic value-vs-weight tradeoff. Example: Ones and Zeroes.
• Unbounded variant: same recurrence but iterate j forward so each item can be reused. Example: Coin Change II.
• Minimize-difference / closest-to-half: find the subset sum closest to total/2 to balance two groups. Example: Last Stone Weight II.