343. Partition Equal Subset Sum
You are given an array of positive integers nums. Decide whether the array can be split into two groups whose sums are equal. Every element must land in exactly one of the two groups — nothing is left out, nothing is used twice.
Return true if such a split exists and false otherwise.
Equivalently: is there a subset of nums whose sum is exactly half of the total? If you find one, the leftover elements automatically form the other half.
Example 1:
Input: nums = [1, 5, 11, 5]
Output: true
Explanation: Total is 22, so each side must sum to 11. The subset {11} works, leaving {1, 5, 5} which also sums to 11.
Example 2:
Input: nums = [1, 2, 3, 5]
Output: false
Explanation: Total is 11, an odd number — it can never be divided into two equal integer halves.
Constraints:
- 1 ≤ nums.length ≤ 200
- 1 ≤ nums[i] ≤ 100
Hints:
Add everything up first. If the total is odd, no split is possible — you can answer immediately. If it is even, the real question is: can some subset hit total / 2?
"Can a subset reach sum s?" is a classic 0/1 decision: each element is either taken or skipped. Trying both choices for every element explodes to 2^n paths, but the state (index, remaining sum) repeats constantly.
Build a boolean table reachable[s] = "some subset sums to s". Process one number x at a time and sweep s from high to low, setting reachable[s] |= reachable[s - x]. The downward sweep is what stops x from being used twice.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 5, 11, 5]
Expected output: true