Partition equal subset sum
HardSubset sum for half the total
Problem
Return whether the array can be split into two subsets of equal sum.
Ask if some subset sums to half the total — a classic subset-sum yes/no.
The idea
Two equal halves each sum to total/2, so the question is whether any subset reaches that value. An odd total is immediately impossible, which is the cheap early exit.
The trick
- Odd total means no.
- Reduces exactly to subset-sum with target = total/2.
- O(n × total/2).
items4
Step 1 of 6. Brute force: for each of the 4 items, branch into "skip it" or "take it". items 4.
1/6
Brute force
timeO(2ⁿ)spaceO(n)
2ⁿ decision tree.
1function go(i, sum) {2 if (i === n) return sum === total / 2;3 return go(i + 1, sum) || go(i + 1, sum + nums[i]);4}Input
- nodes
- 1, 0 edges
Memory
- items
- 4
- branches
- —
- subsets
- —
Call stack
- 0visit(start)
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 5, 11, 5]
- Output:
- true
- Explanation:
- {1,5,5} and {11} each sum to 11.
Example 2
- Input:
- nums = [1, 2, 3, 5]
- Output:
- false
- Explanation:
- Odd total → impossible.
Example 3
- Input:
- nums = [2, 2]
- Output:
- true
- Explanation:
- Split into {2} and {2}.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.