Dynamic Programming · LC #416
Partition Equal Subset Sum
Reduce to 0/1 Knapsack: can a subset sum to `total/2`? Use a 1D boolean DP array traversed right-to-left per element to prevent reuse of the same item.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an integer array `nums`, return `true` if it can be partitioned into two subsets with equal sum.
Sample I/O
Input: nums = [1,5,11,5] Output: true ([1,5,5] and [11]) Input: nums = [1,2,3,5] Output: false
Intuition
How to Think About It
Intuition
If the total sum is odd, an equal split is impossible. Otherwise, finding one subset that sums to `total/2` implicitly defines the other. This is the canonical 0/1 Knapsack feasibility question.
Core Concept
`dp[j]` = true if some subset of processed elements sums to `j`. For each element `n`, iterate `j` from `target` down to `n`: `dp[j] |= dp[j-n]`. Reverse iteration ensures each element is used at most once.
When to use
Any "can we form sum T from a subset" question with each element used at most once. Also a building block for problems like Target Sum (LC 494) and Last Stone Weight II (LC 1049).
When NOT to use
When elements can be reused (use Coin Change / unbounded knapsack with forward iteration). When the target is very large (exponential dp array size - consider meet-in-the-middle).
Key Insights
What to Know Cold
- Early return if total is odd - no valid partition exists.
- Right-to-left inner loop is the hallmark of 0/1 Knapsack - prevents an item from being counted twice in one pass.
- dp[0] = true is the base: the empty subset always sums to 0.
- Can prune: if any single element > target, return false immediately.
- Bitset DP (Python `int` as bitmask) can be faster: `bits |= bits << n` in one line.
1 example
Worked Examples
Partition [1,5,11,5] into equal halves
Total = 22, target = 11. Can a subset sum to 11?
0/1 Knapsack: boolean DP array, reverse inner iteration.
Output: true
The prototypical 0/1 Knapsack interview problem; mastering the reverse-iteration pattern unlocks a whole family of subset-sum problems tested at Amazon and Google.