Frontend Beauty
ESC

Type to search the knowledge base.

Combination Sum

Backtracking to all unique combinations that sum to target — reuse allowed, sort + prune, and Combination Sum II contrast.

intermediate3 min read
  • dsa
  • backtracking
  • interview
  • Google
  • Meta

The problem

Distinct positive integers candidates. Find all unique combinations that sum to target. You may reuse the same number unlimited times. Order of numbers in a combo doesn’t create duplicates ([2,2,3] once, not permutations).

candidates = [2, 3, 6, 7], target = 7
→ [[2,2,3], [7]]

Brute force

Generate all multisets / all sequences and filter — wasteful. Backtracking with an index avoids permutations of the same multiset.

Optimal: backtracking with start index

function combinationSum(
  candidates: number[],
  target: number
): number[][] {
  candidates.sort((a, b) => a - b); // enables prune
  const res: number[][] = [];
  const path: number[] = [];

  function dfs(start: number, remain: number) {
    if (remain === 0) {
      res.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      const c = candidates[i];
      if (c > remain) break; // prune
      path.push(c);
      // reuse allowed → pass i, not i+1
      dfs(i, remain - c);
      path.pop();
    }
  }

  dfs(0, target);
  return res;
}
Time exponential in target/min(coin); prune helps
Space O(target/min) depth + output

Why start and reuse i?

  • Always pick candidates at index ≥ start → combinations stay non-decreasing → no permutation dupes.
  • Passing i (not i+1) allows reusing candidates[i].

Walk target=7, [2,3,6,7]

2 → 2 → 2 → 2 > remain stop
2 → 2 → 3 = 7 ✓
2 → 3 → 2 would be same as 2,2,3 but start index prevents reordering
3 → ...
6 → 6 < 7, next ≥ 6 too big
7 → 7 ✓

Contrast: Combination Sum II

Candidates may have duplicates, each used at most once. Sort, pass i+1, skip equal neighbors at same depth:

// sketch difference only
// if (i > start && candidates[i] === candidates[i-1]) continue;
// dfs(i + 1, remain - c);

Edge cases

  • Empty candidates
  • Target smaller than min candidate → []
  • Single candidate equals target
  • Large target — discuss pruning and output size

Common mistakes

  • Using permutations (swap-based) and deduping with a Set of joined strings
  • Passing i+1 when reuse is required
  • Forgetting to copy path when pushing to res

Interview delivery

  1. Unlimited reuse, unique combos.
  2. Sort + backtrack + start index.
  3. Prune when c > remain.
  4. Mention Sum II difference.
  5. Complexity is output-sensitive exponential.

Mental model

You’re exploring a decision tree: for each position in candidates (from start onward), either skip or take (and stay allowed to take again). Sorting + non-decreasing order means each multiset appears once.

Difference matrix interviewers care about:

Problem Reuse Duplicates in input Skip equals?
Combination Sum yes no n/a
Combination Sum II no yes yes at same depth
Combination Sum III no fixed 1..9 k numbers

Pruning that matters

After sort, if (c > remain) break kills an entire suffix. Without sort you can only continue. Always sort in this problem unless constraints forbid.

Out-loud answer

“Unlimited reuse, unique combinations. Sort, backtrack with start index, pass i to allow reuse, prune when candidate exceeds remain. Push a copy of path when remain hits 0. Exponential output size; pruning helps constants.”

Further reading