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.
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
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
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.