PPractick

The problem

A budgeting app lists the prices of items a user is considering and asks: in how many different ways can they pick items whose total is exactly K? Two picks count as different if they use different positions, even when the values are equal, and prices can be 0 (free items), which doubles the number of ways. The recursive pick/skip count is the natural first answer, but it is exponential. Since the sums are bounded, the same recursion turns into an O(n · K) DP over "number of ways to reach each sum", with the answer reported modulo 10⁹ + 7.

Example: [5, 2, 3, 10, 6, 8], K = 10 → 3 ({2, 8}, {10}, {5, 2, 3}).

Function signature

int perfectSum(const vector<int>& arr, int k);  // non-negative values; count modulo 1e9 + 7

Test cases

Input (arr, K)	Output	Explanation
([5, 2, 3, 10, 6, 8], 10)	3	{2, 8}, {10}, {5, 2, 3}
([2, 5, 1, 4, 3], 10)	3	{2, 5, 3}, {2, 1, 4, 3}, {5, 1, 4}
([0, 0, 1], 1)	4	Each 0 can be in or out
([1, 1, 1], 2)	3	Positions are distinct
([3], 5)	0

(Confirm: values are non-negative; subsequences are counted by positions; the empty subsequence counts when K = 0.)

How interviewers phrase it

• "Count the number of subsets with sum equal to K" (GeeksforGeeks "Perfect Sum Problem").
• In a recursion interview, the first expected answer is the pick/skip count, followed by memoization.

Clarifying questions to ask

1. Can values be 0 or negative? (Zeros matter; negatives break the pruning and the DP bounds.)
2. Are subsets distinguished by position or by value?
3. Is the answer taken modulo something?

Follow-ups to expect

1. "Recursive count?"
2. "Why not stop as soon as sum == K?"
3. "How do you make it polynomial?"
4. "Why iterate s downward?"
5. "Complexity?"

Related questions

• Check if there exists a subsequence with sum K Easy
• Generate Binary Strings Without Consecutive 1s Medium
• Generate Parentheses Medium
• Power Set Medium
• Combination Sum Medium
• Combination Sum II Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in