Combination Sum III

New·#216·Medium·Recursion

k distinct digits from 1–9 summing to n

Asked at:AmazonMicrosoftAdobe

Practice mode

Step

Initialization

Find every set of exactly 3 distinct digits from 1–9 that sums to 7. Because each call starts from one past the digit just used, combinations come out sorted and never repeat.

Recursion workspace

Backtracking with Pruning

Step 1 / 68init

100%

target

curr

[]

[]need 7

digits 1–9, each once, chosen in increasing order · pick i → recurse from i+1 with sum − i · sum = 0 with exactly k digits collects a combination

ans

empty

Explanation

Digits 1–9, each usable at most once, always chosen in increasing order — so combinations come out sorted and never repeat.

step 1 / 68

Space play← → stepHome reset

TimeO(C(9, k) · k)·SpaceO(k)

Backtracking with Pruning

1function func(sum, last, nums, k, ans) {
2  // Exactly k digits and the target hit
3  if (sum === 0 && nums.length === k) {
4    ans.push([...nums]);
5    return;
6  }
7 
8  // Overshot the sum, or used too many digits
9  if (sum <= 0 || nums.length > k) return;
10 
11  for (let i = last; i <= 9; i++) {
12    if (i <= sum) {
13      nums.push(i);
14      func(sum - i, i + 1, nums, k, ans);
15      nums.pop();
16    } else {
17      // Digits only grow — nothing later can fit
18      break;
19    }
20  }
21}
22 
23function combinationSum3(k, n) {
24  const ans = [];
25  const nums = [];
26  func(n, 1, nums, k, ans);//k: 3n: 7
27  return ans;
28}

Command Palette

Combination Sum III

Combination Sum III