Combination Sum II
Medium · Backtracking
You are given a list of positive integers, which may contain repeated values, and a target integer. Find every distinct group of numbers from the list that adds up exactly to the target, where each element in the list may be used at most once per group (position matters for usage, not for what counts as distinct). Return the collection of such groups, without including the same combination of values more than once. The order of groups, and the order of numbers inside a group, does not matter.
Examples
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Why: Each listed group of numbers from the array adds up to 8, using each position in the array at most once, and no duplicate group appears twice.Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
Why: Three of the value-2 entries plus the 1 makes 5, and the single 5 also makes 5; other arrangements would just repeat these same groups.Input: candidates = [3,3,3], target = 9
Output: [[3,3,3]]
Why: All three entries must be used together since each is 3 and the target is 9, and there is only one way to pick them since they occupy distinct positions but yield the same combination.Constraints
1 <= candidates.length <= 100, 1 <= candidates[i] <= 50, 1 <= target <= 30
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Combination Sum II. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.