Partition Equal Subset Sum
Medium· 0/1 knapsack
Problem
Given an array of positive integers, decide whether it can be split into two groups with equal sums. Every element must go into exactly one group.
Examples
Input: nums = [1,5,11,5]
Output: true
[1,5,5] and [11] both sum to 11.
Input: nums = [1,2,3,5]
Output: false
Constraints
- • 1 <= nums.length <= 200
- • 1 <= nums[i] <= 100
Hints & approach
Hint 1
If the total is odd, the answer is immediately false.
Hint 2
Otherwise you need a subset that sums to exactly half the total.
Hint 3
Use a boolean reachable[s] array and add each number once, iterating s downward.
Approachtry the hints first
Reduce to 0/1 subset sum with target = total / 2. Let can[s] mean some subset of processed numbers sums to s, with can[0] = true. For each number x, update s from target down to x: can[s] = can[s] || can[s-x]. Iterating downward ensures each number is used at most once. Return can[target].
Time O(n·sum) · Space O(sum)