LeetCode 39 · Backtracking · Recursion

Combination Sum

MediumAll combinations summing to a target — numbers may be reused.
Given an array of distinct integers candidates and a target, return all unique combinations of candidates that sum to the target. The same number may be chosen an unlimited number of times.

Walkthrough

try:
Pick numbers (with repetition) that sum to the target. Backtrack when you hit or overshoot 0.
candidates
2
3
6
7
path
[]
remain
7
combinations · 0
(none yet)
1
function combinationSum(cands, target) {
2
  const res = [], path = [];
3
  function backtrack(start, remain) {
4
    if (remain === 0) { res.push([...path]); return; }
5
    if (remain < 0) return;
6
    for (let i = start; i < cands.length; i++) {
7
      path.push(cands[i]);
8
      backtrack(i, remain - cands[i]);  // reuse i
9
      path.pop();                       // undo
10
    }
11
  }
12
  backtrack(0, target);
◄
13
  return res;
14
}
target = 7
step 0 / 75
line 12
backtrack(0, 7)
Build combinations that add up to 7. Numbers may be reused; each recursion subtracts a choice from the remaining target.

Intuition

Instead of tracking the running sum, track what is LEFT (remain). Choosing a number simply subtracts it from remain — and remain = 0 means success.

Two base cases fall out naturally: remain == 0 → record the path; remain < 0 → you overshot, so prune this branch immediately.

Because a number can be reused, recurse with i (not i + 1) — the same candidate stays available at the next level.

Passing start = i (never going backwards) is what prevents duplicates like [2,3] and [3,2] from both appearing.

The algorithm

  1. 01Call backtrack(0, target) with an empty path.
  2. 02If remain == 0, record a copy of the path and return.
  3. 03If remain < 0, return (prune).
  4. 04For each candidate from start: push it, recurse with (i, remain − candidate), then pop.

Reference implementation

1
function combinationSum(candidates, target) {
2
  const res = [], path = [];
3
  function backtrack(start, remain) {
4
    if (remain === 0) { res.push([...path]); return; }
5
    if (remain < 0) return;                  // overshot -> prune
6
    for (let i = start; i < candidates.length; i++) {
7
      path.push(candidates[i]);
8
      backtrack(i, remain - candidates[i]);  // i, not i+1 -> reuse allowed
9
      path.pop();
10
    }
11
  }
12
  backtrack(0, target);
13
  return res;
14
}

Complexity

Time
Exponential in the worst case — roughly O(n^(target/min)); pruning keeps it practical.
Space
O(target/min) recursion depth.