Count subsets with sum K
HardAdd the two branches instead of OR-ing them
Problem
Count the number of subsets that sum to exactly k.
Count subsets reaching each sum, adding the ways with and without each number.
The idea
Identical recursion to subset-sum, but combine the take and skip branches with addition to count ways rather than existence. Zeros in the array double the count, since including or excluding them both work.
The trick
- dp[i][s] = dp[i-1][s] + dp[i-1][s - nums[i]].
- Handle zeros deliberately — each doubles the number of ways.
- Take the modulus if the count can grow large.
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 === k ? 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, 2, 2, 3], k = 3
- Output:
- 3
- Explanation:
- Subsets {1,2},{1,2},{3} → 3 ways.
Example 2
- Input:
- nums = [0, 0, 1], k = 1
- Output:
- 4
- Explanation:
- The two 0s can be in or out → 4 ways.
Example 3
- Input:
- nums = [1, 1], k = 2
- Output:
- 1
- Explanation:
- Only {1,1} → 1 way.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.