Combination Sum

New·#39·Medium·Recursion

Reuse candidates freely to hit the target

Asked at:AmazonGoogleMicrosoftMeta

Practice mode

Step

Initialization

Walk the candidates from the back. At each one, either drop it for good (index moves down) or take it and stay put so it can be taken again. Reaching sum = 0 collects a combination.

Recursion workspace

Pick / Drop Recursion

Step 1 / 80init

100%

candidates

[2,3,6,7]

target

curr

[]

[]need 7

walk candidates from the back · drop i → index i−1 · take i → stay at i (so it can repeat) · sum = 0 collects a combination

ans

empty

Explanation

A candidate may be reused, so taking one does not advance the index — only dropping one does. Staying put is what allows repeats without producing the same combination twice.

step 1 / 80

Space play← → stepHome reset

TimeO(2^(target/min))·SpaceO(target/min)

Pick / Drop Recursion

1function func(v, i, sum, v2, ans) {
2  // Target met exactly
3  if (sum === 0) {
4    ans.push([...v2]);
5    return;
6  }
7 
8  // Overshot, or no candidates left
9  if (sum < 0 || i < 0) {
10    return;
11  }
12 
13  // Drop candidate i entirely
14  func(v, i - 1, sum, v2, ans);
15 
16  // Take candidate i — index stays, so it can repeat
17  v2.push(v[i]);
18  func(v, i, sum - v[i], v2, ans);
19 
20  // Undo
21  v2.pop();
22}
23 
24function combinationSum(candidates, target) {
25  const ans = [];
26  const v2 = [];
27  func(candidates, candidates.length - 1, target, v2, ans);//target: 7ans: []
28  return ans;
29}

target7

ans[]

Command Palette

Combination Sum

Combination Sum