#416
Partition Equal Subset Sum
Medium 0/1 knapsack (subset sum)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether the array can be split into two subsets with equal sums.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can the numbers be split into two equal-sum halves?
Why this works: find a subset summing to total / 2 — 0/1 knapsack with a boolean array, looping sums downward so each number is used once.
Example: [1, 5, 11, 5], target 11
reachable after 1: {0,1}; after 5: {0,1,5,6}; after 11: {…,11} ✓ → true✦Hints open one at a time
If the total is odd, it's impossible.
Otherwise: is there a subset that sums to total / 2? That's 0/1 knapsack.
With a 1D boolean array, loop the sum downwards so each number is used once.
↗Approach
can[s] = some subset sums to s. Start with can[0] = true. For each number x, for s from target down to x: can[s] |= can[s − x].
</>Solution (Java)
class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
for (int x : nums) total += x;
if (total % 2 == 1) return false;
int target = total / 2;
boolean[] can = new boolean[target + 1];
can[0] = true;
for (int x : nums) {
for (int s = target; s >= x; s--) { // downwards: each item once
can[s] |= can[s - x];
}
}
return can[target];
}
}!Common mistake
Looping s upwards, which lets the same number be used many times (that's unbounded knapsack).
Complexity
- Time: O(n · target).
- Space: O(target).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon