Combination Sum

Examples

Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]

2 + 2 + 3 = 7, using the 2 twice. And 7 by itself also works.

Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Three different ways to reach 8 using repeats of 2 and/or 3.

Input: candidates = [2], target = 1
Output: []

No combination of 2s can ever add up to 1.

Constraints

• 1 <= candidates.length <= 30

• 2 <= candidates[i] <= 40

• All elements of candidates are distinct.

• 1 <= target <= 40

Approach

Think of building a combination one number at a time, always deciding "which candidate do I add next?" Since repeats are allowed, after adding a candidate you're allowed to add that exact same one again - but to avoid producing the same combination in a different order, you only move forward through the candidate list, never backward.

A straightforward version of this explores every candidate at every step, only stopping once the running total exactly matches the target (a valid combination) or exceeds it (a dead end that gets abandoned). After trying a candidate, you "un-add" it - remove it from the running combination - before trying the next one, which is exactly the choose/explore/un-choose pattern of backtracking.

You can make the same search noticeably faster with one extra trick: sort the candidates first. Once they're in order, as soon as adding the next candidate would already overshoot the target, every candidate after it (being even bigger) would overshoot too - so you can stop trying candidates at that step entirely, instead of checking each one individually.

Solutions

Backtracking — Try Every Candidate

At every step, loop over all candidates starting from the current index onward (allowing the current index to repeat). Add a candidate to the running combination, recurse with that same starting index (since it can be reused) and a smaller remaining target, then remove it before trying the next candidate. Stop a path as soon as the remaining target hits zero (success) or goes negative (dead end).

function combinationSum(candidates, target) {
  const result = [];
  const current = [];

  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }
    if (remaining < 0) {
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      backtrack(i, remaining - candidates[i]); // i, not i + 1: reuse allowed
      current.pop();
    }
  }

  backtrack(0, target);
  return result;
}

Time: O(2^target) in the worst case · Space: O(target / min(candidates)) recursion depth, plus output storage

Optimal — Sort and Prune

Sort the candidates first. Then, at each step, skip any candidate that would already push the running total past the target - and since the list is sorted, every candidate after it is at least as large, so you can stop checking that branch entirely instead of testing each one and discovering it fails.

function combinationSum(candidates, target) {
  const sorted = [...candidates].sort((a, b) => a - b);
  const result = [];
  const current = [];

  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }

    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break; // every candidate after this is even bigger

      current.push(sorted[i]);
      backtrack(i, remaining - sorted[i]);
      current.pop();
    }
  }

  backtrack(0, target);
  return result;
}

Time: O(2^target) worst case, but far fewer branches explored in practice · Space: O(target / min(candidates)) recursion depth, plus a sorted copy of the input