DSA interview question

Count Subsets with Sum K

Hard · Algorithms · Topics: dynamic programming, knapsack

The problem

You're building a "grant allocation validator" for a nonprofit's finance system. Given an array of donation amounts arr and a target grant amount K, the finance team wants to know how many distinct combinations of donations could have been bundled together to exactly fund a grant of size K — useful for auditing which donation groupings are even mathematically possible before manually verifying paperwork. Given array arr and integer K, return the number of subsets of arr whose sum equals K.

Function signature

int countSubsetsWithSumK(vector<int>& arr, int K);

Test cases

`arr`	`K`	Output	Explanation
`[1,2,3,3]`	6	3	{1,2,3}, {1,2,3} (using the other 3), {3,3} — 3 distinct subsets sum to 6
`[1,1,1,1]`	2	6	choose any 2 of the four 1s → C(4,2) = 6
`[5]`	5	1	{5} itself
`[5]`	0	1	empty subset — sums to 0
`[]`	0	1	empty array, target 0 → one way: the empty subset
`[]`	5	0	empty array, positive target unreachable
`[0,0,1]`	1	4	zeros can be freely included or excluded without affecting sum — classic doubling trap

(Note: the empty subset always counts toward K=0 — a very common off-by-one/base-case trap if not handled carefully.)

How interviewers phrase it

"Given an array and a target sum K, count the number of subsets that sum to K."
"How many different ways can you select elements from this array (each used at most once) to total exactly K?"
Often introduced as the foundational building block before Target Sum / Partition problems — expect it to be a stepping stone rather than the final question in the interview.

Clarifying questions to ask

Does the empty subset count if K = 0? (Standard convention: yes, exactly one way.)
Can array elements be 0? (Important — zeros don't affect sum reachability but still create genuinely distinct subsets, since "included" vs "excluded" 0 are different selections.)
Are elements guaranteed non-negative? (Standard assumption for this classic formulation — negative numbers would require a different DP indexing scheme.)
Can the same value appear multiple times in arr? (Yes, typically — duplicates are treated as distinct elements by position, even if their values are equal.)
What's the expected range of K and array size? (Signals whether O(n·K) DP is acceptable, and what capacity the DP array needs.)

Follow-ups to expect

"Can you optimize space?"
"How does this relate to Target Sum / Count Partitions with Given Difference?"
"What if you needed to return the actual subsets, not just the count?"
"What if the array could contain negative numbers?"
"Can counts overflow, and how would you handle very large counts?"
"Is there a way to solve this with combinatorics (nCr) instead of DP for special cases?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview