Count all subsequences with sum K
EasyTake / not-take, returning counts
Problem
Count the number of subsequences of an array whose elements sum to exactly K.
For each element choose take-or-skip, counting the ways the remaining target reaches zero.
The idea
Recurse on index and remaining target, returning the number of ways from that state: the count for taking the element plus the count for skipping it. At the end, a remaining target of zero is one valid way.
The trick
- Return 1 when the target reaches 0 at the base case, 0 otherwise.
- Memoise on (index, target) to collapse the exponential blow-up.
- Zeros in the array double the count of each way — handle them deliberately.
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, 1], k = 2
- Output:
- 2
- Explanation:
- {2} and {1,1} → 2 subsequences.
Example 2
- Input:
- nums = [1, 1, 1], k = 2
- Output:
- 3
- Explanation:
- Any two 1s → 3 ways.
Example 3
- Input:
- nums = [2], k = 3
- Output:
- 0
- Explanation:
- Can't reach 3 → 0.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.