DSA interview question
An expense-report tool has a list of receipt amounts, some equal, and needs every way to pick receipts whose total is exactly the reimbursement target, each receipt used at most once. Two picks with the same multiset of amounts count as the same combination, even if they use different receipts with equal amounts. The fix is to sort the amounts and, at each level of the recursion, try each distinct value only once. That skips duplicate branches before they start, instead of generating everything and de-duplicating afterwards.
Example: [10, 1, 2, 7, 6, 1, 5], target 8 → [1,1,6] [1,2,5] [1,7] [2,6].
vector<vector<int>> combinationSum2(vector<int> candidates, int target); // lexicographic order
Input (candidates, target) | Output | Explanation |
|---|---|---|
([10, 1, 2, 7, 6, 1, 5], 8) | [1,1,6] [1,2,5] [1,7] [2,6] | [1,7] appears once even though there are two 1s |
([2, 5, 2, 1, 2], 5) | [1,2,2] [5] | |
([1, 1, 1], 2) | [1,1] | |
([3], 2) | (none) | |
([2, 2, 2], 4) | [2,2] |
(Confirm: candidates are positive and may repeat; each position is used at most once; combinations must be unique as multisets.)
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 interviewAll 474 dsa interview questions
DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in