Subset Sum
MediumExplore include/exclude, prune on target
Try including or excluding each number to see which combinations add up to the target.
The idea
Recurse choosing to include or exclude each number, tracking the remaining target. Prune branches that overshoot. It's the include/exclude pattern with an accumulator.
2
3
5
0
1
2
Step 1 of 4. Can a subset of [2,3,5] sum to 5? Try include / exclude with pruning. Values: 2, 3, 5.
1/4
Optimal
timeO(2ⁿ)spaceO(n)
Cut branches past the target.
1function go(i, remaining) {2 if (remaining === 0) return true;3 if (i === n || remaining < 0) return false;4 return go(i + 1, remaining - a[i]) // take5 || go(i + 1, remaining); // skip6}Input
- array
- [2, 3, 5]
Memory
- remaining
- —
Output
- remaining
- —
- found
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3, 4], target = 6
- Output:
- true
- Explanation:
- 2+4 (or 1+2+3) makes 6.
Example 2
- Input:
- nums = [1, 2, 7], target = 6
- Output:
- false
- Explanation:
- No subset sums to 6 → false.
Example 3
- Input:
- nums = [5], target = 5
- Output:
- true
- Explanation:
- The single 5 works.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.