The 0/1 Knapsack problem captures a fundamental trade-off: given a set of items each with a weight and a value, and a container with a fixed capacity, choose which items to include so that the total value is maximized without exceeding the capacity. The "0/1" means each item is either taken (1) or skipped (0). No fractions, no duplicates.

Many problems reduce to knapsack. Subset sum, partition problems, target sum, and some string problems all share the same core decision: pick or skip items to hit a capacity constraint. Learning the knapsack framework makes an entire class of DP problems approachable.

You have n items, where item i has weight w[i] and value v[i], and a knapsack with capacity W. Find the maximum total value you can carry without exceeding W. Each item can be used at most once.

The "0/1" distinction matters. The unbounded variant allows taking an item multiple times; the fractional variant allows fractions (solved by greedy). The 0/1 version is the hardest because taking the highest value-per-weight item first does not guarantee an optimal solution. You need to consider all combinations, which is where DP comes in.

The decision tree for a small example with 3 items and capacity 5:

The tree has 2^n leaves, but different paths can arrive at the same state (same remaining capacity, same items left). This overlapping substructure is what makes DP applicable.

Not every DP problem is a knapsack problem, but many are. The signals:

When these signals appear together, think knapsack.

The items, capacity, and "value" change between problems, but the core decision, take or skip each item against a capacity, stays the same.

State Definition

Define dp[i][w] as the maximum value achievable using the first i items with a knapsack capacity of w.

Transition

For each item i, we have two choices:

We pick whichever is larger:

Base Cases

Filling the Table

Fill row by row, left to right. Each cell depends on two cells from the previous row: one directly above (skip) and one shifted left (take).

This dependency pattern enables the space optimization.

Space Optimization: 2D to 1D

Since each row only depends on the previous row, we do not need the entire 2D table. A single 1D array of size W+1 is enough. There is a catch though.

If we iterate capacity from left to right (0 to W), then when we compute dp[w], the value at dp[w - w[i]] has already been updated in the current iteration. That means we would be using item i's contribution twice, effectively solving the unbounded knapsack instead.

Iterate capacity from right to left (W down to w[i]). When we read dp[w - w[i]], it still holds the value from the previous row (before item i was considered).

Right-to-left iteration in the 1D array ensures each item is used at most once.

Problem Statement

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of elements in both subsets is equal.

Example: nums = [1, 5, 11, 5] returns true because [1, 5, 5] and [11] both sum to 11.

Constraints: 1 <= nums.length <= 200, 1 <= nums[i] <= 100

Intuition

At first glance, this looks like a partitioning problem, not a knapsack problem. Reframe it.

If the total sum of all numbers is S, then we need two subsets that each sum to S/2. If S is odd, there is no valid partition, so we return false immediately.

The problem becomes: can we find a subset of nums that sums to exactly S/2?

This is a subset sum problem, which is a special case of 0/1 knapsack:

Instead of tracking maximum value, our DP tracks reachability: dp[w] is true if some subset of the numbers seen so far sums to exactly w.

The transition becomes:

If we could already reach sum w (skip the current number), or if we could reach w - nums[i] (take the current number to bridge the gap), then sum w is achievable.

Step-by-Step Trace

Trace through nums = [1, 5, 11, 5].

Total sum = 22, target = 11.

We use a 1D boolean array dp[0..11], initialized with dp[0] = true (empty subset sums to 0).

We can stop early. dp[11] is true, so the partition exists. The third number (11) by itself forms one subset, and [1, 5, 5] forms the other.

Iterating right-to-left prevented us from using the same number twice. When we processed nums[0] = 1, we did not set dp[2] = true (which would have meant using the number 1 twice).

Implementation

The space-optimized 1D solution:

Complexity Analysis

A note on pseudo-polynomial complexity

O(n * target) looks polynomial, but target is a value, not the size of the input. The number of bits needed to represent target is log(target), so the runtime is `O(n 2^log(target)), exponential in the input length.

This is called pseudo-polynomial: fast when values are small (target up to 10^4-10^6), infeasible when values are large (target = 10^18). 0/1 Knapsack and Subset Sum are both NP-complete in the strong sense of weight magnitude; the DP works only because the typical interview constraints keep target` small. A common follow-up: "What if the weights can be up to 10^9?"

Partition Equal Subset Sum is one of a family of problems that all reduce to 0/1 knapsack with small variations. Recognizing the family is the difference between solving a new problem in five minutes and re-deriving the recurrence under interview pressure. The shared template is always:

dp[i][w] = combine( dp[i-1][w], dp[i-1][w - weight[i]] (with item i applied) )

What changes between problems is what dp[i][w] stores and how combine aggregates the two options. Once that mapping is clear, the code is identical up to the aggregator.

The Family

How To Recognize Each One In An Interview

The Target Sum Reduction

LC 494 (Target Sum) asks: given an array nums and an integer target, how many ways are there to assign + or - to each number so the sum equals target?

Let P be the subset of numbers assigned +, and N be the subset assigned -. Then:

Adding the two: 2P = totalSum + target, so P = (totalSum + target) / 2.

The problem reduces to: how many subsets of nums sum to (totalSum + target) / 2? This is a count-variant subset sum, aggregator sum.

Edge cases for the reduction:

Recovering The Chosen Items

A frequent follow-up: "Don't just return the maximum value. Return which items achieve it."

Build the DP table as usual. Then walk it backward from dp[n][W]:

The condition dp[i][w] != dp[i-1][w] means including item i changed the answer; therefore item i was used. This recovery walk is O(n) and only works on the 2D table; if you space-optimized to 1D, you lose the ability to reconstruct the chosen items.

In interviews, mention the space-time trade-off: O(W) space or item reconstruction, not both.