Partition Equal Subset Sum
Partition Equal Subset Sum: return true if nums can be split into two subsets with equal sums.
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
Intuition
Partition equal subset sum asks whether an array can be split into two subsets with equal sums. Trying every split is 2ⁿ, but two observations reduce it sharply.
First, an odd total is immediately impossible — two equal integer halves cannot sum to an odd number. That check costs one pass and rejects half of all inputs outright.
Second, if the total is even, the two subsets must each sum to exactly total / 2. And crucially, only one subset needs constructing:
- If some subset sums to half the total, the remaining elements necessarily sum to the other half — so the problem reduces to subset-sum for a single target.
That reduction is the whole insight. It converts a partitioning question into a reachability question.
The DP tracks which sums are achievable. dp[s] is true when some subset sums to s, seeded with dp[0] = true since choosing nothing always reaches zero.
For each number, sweep the sums downward from the target to the number's value. Sweeping upward lets a single number be used repeatedly, silently turning this into unbounded knapsack and reporting true for inputs that cannot actually be partitioned.
The transition is dp[s] = dp[s] or dp[s - num] — a sum is reachable if it already was, or if removing this number leaves a reachable sum.
The answer is dp[target]. An early exit once the target becomes reachable saves work on inputs that succeed quickly.
The cost is O(n × sum), pseudo-polynomial — it scales with the total's magnitude, not just the element count.
Subset-sum on half the total. The odd-total shortcut is free and rules out a large class of inputs instantly. The 1-D boolean array with a descending inner loop is the space-optimised 0/1 knapsack — the direction of that loop is what enforces "each item once".
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n x sum/2) time and O(sum/2) space.
Reject an odd total
Two equal integer halves cannot sum to an odd number, so an odd total returns false immediately. One pass eliminates half of all inputs.
Reduce to a single subset
If one subset sums to half the total, the rest necessarily sums to the other half. This converts partitioning into a subset-sum reachability question.
Define the reachability table
dp[s] is true when some subset sums to s. Seed dp[0] = true, since choosing nothing always achieves zero.
Sweep sums downward
For each number, iterate sums from the target down to that number. Sweeping upward reuses one number repeatedly, silently becoming unbounded knapsack.
Apply the transition
dp[s] = dp[s] or dp[s - num] — a sum is reachable if it already was, or if removing this number leaves a reachable sum.
Exit early when found
Return true as soon as the target becomes reachable. This costs nothing and saves the remaining sweeps on inputs that succeed early.
Cost of the tabulation
Each number sweeps the target range, giving O(n × sum) time and O(sum) space — pseudo-polynomial, scaling with the total's magnitude.
Solution & live demo
Common pitfalls
Iterating the inner loop forwards
for t in range(x, target + 1):
for t in range(target, x - 1, -1):
Going forwards, dp[t - x] may already reflect the current item, so the same number gets used repeatedly — that's the unbounded knapsack. Descending guarantees every read comes from the previous item's row.
Skipping the odd-total check
target = total // 2
if total % 2:
return False
target = total // 2An odd total can't split into two equal halves, and integer division silently rounds down to a target that isn't half of anything. The check is both a correctness guard and an instant exit.
Not seeding dp[0]
dp = [False] * (target + 1)
dp = [False] * (target + 1) dp[0] = True
The empty subset sums to 0, and that's the base every other reachable sum is built from. Without it the whole array stays false and every input returns False.
Edge cases
Return false immediately; no even split of an odd number exists.
Harmless — zero contributes nothing and the reachable sums are unchanged.
It can never be placed on either side without exceeding the target, so dp[target] stays false and the answer is false.
This is the classic bug: it permits reusing an element and returns true for inputs like [1,2,5] where no valid split exists. Always iterate downward for 0/1 knapsack.