DP — Partition Equal Subset Sum
↗ LeetCode: Partition Equal Subset Sum · Medium · pattern chapter →
Can nums split into two subsets with equal sum?
Example 1 — nums=[1,5,11,5] → true ([1,5,5] vs [11], sum=11 each) Example 2 — nums=[1,2,3,5] → false (sum=11, odd → impossible) Example 3 — nums=[2,2] → true
Constraints — 1 ≤ n ≤ 200; 1 ≤ nums[i] ≤ 100. Brute is 2ⁿ subsets — 2²⁰⁰ ops = universe-age. Knapsack DP is O(n·sum) ≤ 200·10⁴ = 2·10⁶ ops = 50ms.
Interview timer00:00
Approach 1 — Brute subset enumeration
Intuition. Try every subset; if its sum is total/2, return true. 2ⁿ combinations.
Complexity — Time O(2ⁿ); Space O(n) stack. TLE past n=25. In an interview say "reduce to subset-sum feasibility — knapsack DP → O(n·sum)."
Approach 2 — Subset-sum DP (0/1 knapsack, canonical)
Insight. Possible iff sum even AND a subset sums to sum/2. Boolean DP dp[j] = "can we hit sum j?".
Trap — iterate j descending for 0/1 knapsack (else you'd count each item multiple times).
boolean canPartition(int[] nums) {
int sum = 0; for (int x : nums) sum += x;
if (sum % 2 == 1) return false;
int t = sum / 2;
boolean[] dp = new boolean[t + 1];
dp[0] = true;
for (int x : nums)
for (int j = t; j >= x; j--)
dp[j] |= dp[j - x];
return dp[t];
}Complexity — Time O(n · sum); Space O(sum). Say aloud in an interview: "canonical 0/1 knapsack — same skeleton as Target Sum, Last Stone Weight II."
BitSet speedup
dp |= dp << x on BitSet — word-parallel.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute subsets | O(2ⁿ) | O(n) | TLE past n=25 |
| 0/1 knapsack DP | O(n · sum) | O(sum) | Canonical |
| BitSet | O(n · sum / 64) | O(sum) | Polish |
When to use which
- Two equal subsets → this.
- k subsets → Partition to K Equal Sum Subsets.
- Return the partition → track parent choices.