Partition Equal Subset Sum
Return true if nums can be split into two subsets with equal sums.
Intuition
Splitting into two equal halves sounds like it needs two decisions per element, but it does not: once you have chosen a subset summing to half the total, the remaining elements automatically form the other half. So the question collapses to 'is there any subset summing to total / 2?' — which is the subset-sum problem, a 0/1 knapsack with the item weight equal to its value. And if the total is odd, no split exists at all, which is a free O(n) rejection before any DP runs.
Approach
Reject the odd case, then reframe
Compute the total. Two equal integer halves must sum to an even number, so an odd total is immediately impossible — return false in O(n). Otherwise let target = total / 2. Because the two subsets partition the array, choosing one determines the other, so we only need to decide whether target is reachable by some subset.
Define the knapsack table
Let dp[t] be true when some subset of the elements considered so far sums to exactly t. Start with dp[0] = true — the empty subset sums to zero — and everything else false. Processing element x, any previously reachable sum t - x makes t newly reachable. This is 0/1 knapsack: each element may be used at most once.
Sweep the table downward to enforce 'at most once'
The 2-D table has one row per element, but each row reads only the row above, so a single 1-D array suffices. The subtlety is the iteration direction: sweep t from target down to x. Going upward would let dp[t] read a slot the current element has already updated, effectively reusing the same element multiple times — that is the unbounded-knapsack recurrence, and it silently gives wrong answers here. Downward guarantees each read comes from before this element was introduced.
Solution & live demo
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.