0/1 Knapsack (DP) Pattern

CodingMid2 min read · 4 problemsUpdated Oct 28, 2026

Choose/skip decisions over items with capacity; tabulate optimal value for subproblems.

When to Use It

Subset sum, partition equal subset sum, target sum, coin change, rod cutting.

Classic example: Partition Equal Subset Sum.

How It Works

0/1 knapsack is the prototype for 'decide include/exclude over n items with a capacity constraint, maximizing value'. The state is (item index, remaining capacity), the transition is max(skip = dp[i+1][c], take = dp[i+1][c - w[i]] + v[i]). Time and space are O(n * C); space can drop to O(C) by iterating capacity from high to low to avoid reusing the same item.

Many problems are knapsack in disguise. Subset sum: values = weights, ask if any subset hits exactly the target. Partition equal subset sum: subset sum with target = total/2. Coin change (unbounded): like knapsack but items have unlimited copies, so iterate capacity low-to-high. Target sum: assign +/- to each number, transform to subset sum via algebra (count subsets summing to (total + target) / 2).

The 1D space optimization is the most common interview ask. Direction matters: iterate capacity high-to-low for 0/1 (each item used at most once); low-to-high for unbounded (each item reusable). Reversing the iteration direction silently changes the semantics, a subtle bug.

Key Insight

Iterating capacity from high to low in the 1D rollover prevents using the same item twice in 0/1 knapsack; reversing the direction enables unbounded knapsack: the same recurrence, different iteration order, different problem.

dp[i][w] = best value using first i items with capacity w. Each cell = max(skip, take).

Templates

// 0/1 knapsack: each item used at most once
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
    for (int s = target; s >= num; s--) {
        dp[s] = dp[s] || dp[s - num];
    }
}
return dp[target];

# 0/1 knapsack: each item used at most once
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
    for s in range(target, num - 1, -1):
        dp[s] = dp[s] or dp[s - num]
return dp[target]

Common Pitfalls

Confusing 0/1 vs unbounded variants and getting the loop direction wrong, double-counting items or missing valid combinations.
For 'count number of ways' variants, initializing dp[0] = 0 instead of dp[0] = 1 (empty subset is one valid way to make target 0).
In target sum, forgetting to check that (total + target) is even and non-negative before dividing, otherwise no valid subset exists.
Mixing 'maximize value' (take max) with 'count ways' (take sum) recurrences.
Iterating items as the inner loop when you want unbounded behavior over permutations (combination sum IV) vs combinations (coin change count), the loop nesting changes the meaning.

Variations

0/1 knapsack: max value with each item at most once.
Unbounded knapsack: coin change (min coins), rod cutting, integer break.
Subset sum / partition equal subset sum: knapsack with capacity = target.
Target sum / +- assignment: transform to subset sum count.
Bounded knapsack (limited copies): expand into 0/1 with copies, or binary decomposition.

Big O

Time: O(n * m)
Space: O(n * m)

The DP table has one row per item (n) and one column per capacity (m = W), each filled in O(1). Space can be compressed to O(m) by keeping only the previous row.

Next PatternTopological Sort