Count partitions with given difference
HardSolve for one subset's sum
Problem
Count ways to split the array into two subsets whose sums differ by d.
Reduce to counting subsets with sum (total-d)/2, since the two parts differ by d.
The idea
If the two subsets sum to s1 and s2 with s1 - s2 = d, then s2 = (total - d)/2. So the answer is the number of subsets summing to that value — a plain count-subsets problem.
The trick
- Impossible when total - d is negative or odd.
- Reduces to count-subsets with the derived target.
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 === need ? 1 : 0;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, 1, 2, 3], d = 1
- Output:
- 3
- Explanation:
- 3 ways to split with difference 1.
Example 2
- Input:
- nums = [5, 2, 6, 4], d = 3
- Output:
- 1
- Explanation:
- One valid partition.
Example 3
- Input:
- nums = [1, 2, 3], d = 0
- Output:
- 2
- Explanation:
- Balanced split → 1 way.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.