PPractick

The problem

A café sells drinks at a few distinct price points, and a customer with a gift card of value target wants to see every way to spend it exactly, buying any drink as many times as they like. Order doesn't matter, so 2 + 2 + 3 and 3 + 2 + 2 are the same combination. Backtracking avoids those duplicates with one rule: once you move past a candidate, you never come back to it. At each step, either use the current candidate again (staying on it) or move on to the next one.

Example: candidates [2, 3, 6, 7], target 7 → [2,2,3], [7].

Function signature

vector<vector<int>> combinationSum(const vector<int>& candidates, int target);

Test cases

Input (candidates, target)	Output	Explanation
([2, 3, 6, 7], 7)	[2,2,3] [7]	2 is reused
([2, 3, 5], 8)	[2,2,2,2] [2,3,3] [3,5]
([2], 1)	(none)
([1], 2)	[1,1]
([3, 4], 10)	[3,3,4]

(Confirm: candidates are distinct positive integers; each can be used any number of times; combinations are unique as multisets; any order of output is fine.)

How interviewers phrase it

• "Given distinct integers and a target, return all unique combinations where the chosen numbers sum to target; the same number may be chosen any number of times" (LeetCode 39).

Clarifying questions to ask

1. Are candidates distinct and positive? (Positive guarantees termination.)
2. Can a number be reused? (Yes, unlimited.)
3. Does the order of combinations or of numbers inside them matter?

Follow-ups to expect

1. "How do you avoid permutations of the same combination?"
2. "How does reuse change the recursion?"
3. "How can you prune?"
4. "What's the complexity?"
5. "What if you only needed the count?"

Related questions

• Generate Binary Strings Without Consecutive 1s Medium
• Generate Parentheses Medium
• Power Set Medium
• Combination Sum II Medium
• Subsets I Medium
• Subsets II Medium

All 474 dsa interview questions

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