0/1 Knapsack DP

The most important 2D DP pattern for subset problems — index × capacity. If you can define dp[i][c] for the first i items with capacity c, you can solve hundreds of problems.

14 min readLeetCode Patterns for InterviewsCode

The Pattern

The 0/1 Knapsack problem: given N items each with weight w[i] and value v[i], maximize total value for a capacity C. Every item is either taken (1) or not (0). The state space is two-dimensional: which item we're considering × remaining capacity.

The recurrence is the heart of the pattern: dp[i][c] = max(dp[i-1][c], v[i] + dp[i-1][c - w[i]]). You skip the item (keep previous best at same capacity) or take it (add its value and reduce capacity by its weight). This same structure appears in subset sum, partition equal subset sum, target sum, and coin change II.

Index × capacity — two dimensions, one recurrence

The knapsack recurrence dp[i][c] = max(skip, take) is the template for all subset-sum DP. Once you derive this, problems like Partition Equal Subset Sum (416) and Target Sum (494) become mechanical: just adapt what dp[i][c] represents.

dp table for weights=[1,2,3], values=[6,10,12], capacity=5

0cap=0

0cap=3

0cap=5

The Template

Go0/1-knapsack-—-2d-and-1d-optimized.go

32 linesLn 1, Col 1Go

2D is easier to reason about: each row i depends only on row i-1. 1D optimization iterates capacity backward to avoid reusing the same item multiple times (that's for unbounded knapsack).

When to Use

Target subset sum: can we sum to exactly target with some subset? (Partition Equal Subset Sum).
Assigning +/- signs to reach a target (Target Sum = subset sum variant).
Counting ways to make change with unlimited or limited coins (Coin Change II).
Two choices per item: take or skip, with a capacity constraint.
n × capacity ≤ 10⁶ — DP table fits in memory.

Problems

#416Partition Equal Subset SumMedium0/1 Knapsack — subset sum to target = total/2 · O(n · target) where target = sum/2 time · O(target) space #494Target SumMedium0/1 Knapsack — subset sum with offset · O(n · target) time · O(target) space #518Coin Change IIMediumUnbounded Knapsack — count combinations (not permutations) · O(n · amount) time · O(amount) space

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.

Stage 1 · Code

Dynamic Programming & Greedy