Combination Sum II

New·#40·Medium·Recursion

Each candidate once, with duplicates skipped

Asked at:AmazonGoogleMicrosoft

Practice mode

Step

Sort the candidates

Each candidate may be used at most once, and the input can repeat. Take a candidate and advance, or reject it and skip straight past all of its duplicates so no combination is built twice.

Recursion workspace

Sort + Skip Duplicates

Step 1 / 101init

100%

candidates

[1,1,2,5,6]

target

curr

[]

[]need 8

sorted so equal values sit together · take advances the index (used once) · reject jumps past every copy · sum = 0 collects a combination

ans

empty

Explanation

Sorted first: [1,1,2,5,6] → [1,1,2,5,6]. Sorting puts equal values next to each other, so when one is rejected every copy of it can be jumped over in a single move.

step 1 / 101

Space play← → stepHome reset

TimeO(2ⁿ · k)·SpaceO(k)

Sort + Skip Duplicates

1function func(ind, sum, nums, candidates, ans) {
2  if (sum === 0) { ans.push([...nums]); return; }
3  if (sum < 0 || ind === candidates.length) return;
4 
5  // Take candidates[ind], then move past it
6  nums.push(candidates[ind]);
7  func(ind + 1, sum - candidates[ind], nums, candidates, ans);
8  nums.pop();
9 
10  // Reject it — and skip every duplicate of it
11  for (let i = ind + 1; i < candidates.length; i++) {
12    if (candidates[i] !== candidates[ind]) {
13      func(i, sum, nums, candidates, ans);
14      break;
15    }
16  }
17}
18 
19function combinationSum2(candidates, target) {
20  candidates.sort((a, b) => a - b);//candidates: [1,1,2,5,6]target: 8
21  const ans = [];
22  func(0, target, [], candidates, ans);
23  return ans;
24}

candidates[1,1,2,5,6]

target8

Command Palette

Combination Sum II

Combination Sum II