Partition Equal Subset Sum
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
