Partition a set into two subsets with minimum absolute sum difference
HardFind every reachable subset sum
Problem
Split the array into two subsets minimizing the absolute difference of their sums.
Find every reachable subset sum, then pick the one closest to half the total.
The idea
Compute which sums are achievable by some subset, then for each reachable s the difference is |total - 2s|. Taking the minimum over all reachable sums answers it without enumerating partitions.
The trick
- Only check s up to total/2 — the halves mirror each other.
- The subset-sum table gives every reachable value at once.
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 Math.abs(total - 2 * sum);3 return Math.min(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, 6, 11, 5]
- Output:
- 1
- Explanation:
- Split into {1,6,5} and {11} → difference 1.
Example 2
- Input:
- nums = [1, 2, 7]
- Output:
- 4
- Explanation:
- {1,2} vs {7} gives gap 4.
Example 3
- Input:
- nums = [1, 1]
- Output:
- 0
- Explanation:
- Even split → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.