Backtracking crash course ↗ · 72

39. Combination Sum

Find all unique combinations of candidates that sum to a target, where each candidate may be reused unlimited times. The key is a backtracking DFS that stays at the same index to allow reuse, and advances the start index at each loop iteration to prevent duplicate sets.

● MediumBacktrackingDecision TreeTypeScript

PROBLEM What we're solving

Given a list of distinct positive integers candidates and a target, return all unique combinations that sum to target. Each candidate may be used any number of times. Order within a combination doesn't matter, but no two combinations in the result may be the same multiset. candidates=[2,3,6,7], target=7 → [[2,2,3],[7]]. There are exactly two ways: three 2’s and a 3, or a single 7.

KEY IDEA Pass the start index forward to prevent duplicates

Insight → to allow reuse of the same candidate, recurse with i (not i+1). To prevent generating the same multiset twice (e.g. both [2,3,2] and [2,2,3]), each recursive call only considers candidates at index start or later — you never go backwards. Sort first so you can prune entire branches early once a candidate exceeds the remaining target.

RECIPE Sort, DFS, reuse with i, skip with i+1

  • 0 · Sort candidates. Ascending order lets you break the inner loop the moment a candidate exceeds the remaining target — everything to the right is also too large.
  • 1 · Base case: remaining = 0. The current path is a valid combination. Copy it into results ([...path]) and return.
  • 2 · Loop from start to end. The start parameter prevents going back to earlier candidates and thus avoids duplicate multisets.
  • 3 · Prune. If candidates[i] > remaining, break — no point continuing (sorted).
  • 4 · Include and recurse. Push candidates[i] onto path, then recurse with dfs(i, …) — same i, not i+1, so this candidate can be reused.
  • 5 · Backtrack. Pop the candidate off the path after the recursive call returns. The loop then advances to i+1, exploring the branch that skips this candidate.
Classic confusion → beginners pass i+1to the recursive call thinking “move forward so we don't repeat.” That prevents reuse — you'd never produce [2,2,3] at all. The correct rule: pass i to permit reuse; the outer loop handles the no-duplicates guarantee by never going backwards.
Pattern transfer → the same start-index technique solves Combination Sum II (candidates with duplicates — sort + skip duplicates at the same depth), Combination Sum III (exactly k numbers), and Subsets / Subsets II (record at every node, not just when remaining = 0).

COST Complexity & pruning impact

No pruning, no sorting
O(n^(t/m))
n candidates, target t, min candidate m. Exponential exploration.
Sorted + prune on exceed
O(n^(t/m))
Same worst case, but the constant is far smaller — pruned branches never expand.

Worst-case time is O(nt/m) where t is the target and m is the smallest candidate (maximum depth t/m, n branches at each level). Space is O(t/m) for the recursion stack plus output. Sorting is O(n log n) but dominates only for tiny inputs.

RUN IT Stay at i to reuse, advance to i+1 to skip

step 0 / 24
STARTStarting backtracking DFS on sorted candidates [2, 3, 6, 7], target = 7.
1function combinationSum(candidates: number[], target: number): number[][] {
2▶  const result: number[][] = [];
3▶  const sorted = [...candidates].sort((a, b) => a - b);
4 
5  function dfs(start: number, path: number[], remaining: number): void {
6    if (remaining === 0) {
7      result.push([...path]);   // found a valid combination
8      return;
9    }
10    for (let i = start; i < sorted.length; i++) {
11      if (sorted[i] > remaining) break; // pruned: sorted, so all further also too large
12 
13      path.push(sorted[i]);
14      dfs(i, path, remaining - sorted[i]); // i not i+1: allow reuse of same candidate
15      path.pop();
16    }
17  }
18 
19▶  dfs(0, [], target);
20  return result;
21}
current path(empty)
State
[2, 3, 6, 7]
sorted
0
start idx
7
remaining
0
depth
[]
combinations
active index / candidate being triedcombination foundbranch prunedcurrent recursion depth
slowfast

TYPESCRIPT The solution, annotated

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

  function dfs(start: number, path: number[], remaining: number): void {
    if (remaining === 0) {
      result.push([...path]);   // found a valid combination
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break; // pruned: sorted, so all further also too large

      path.push(sorted[i]);
      dfs(i, path, remaining - sorted[i]); // i not i+1: allow reuse of same candidate
      path.pop();
    }
  }

  dfs(0, [], target);
  return result;
}

Reading it block by block

Line 3 — sort candidates.Sorting is not required for correctness, but it enables the early-break pruning on line 11. Without it you'd have to check every candidate even when the smallest remaining one already exceeds the target.
Lines 5–8 — base case. When remaining reaches exactly 0, the path is a valid combination. We push a copy ([...path]) because path is mutated as the recursion unwinds.
Lines 9–11 — loop + prune. The loop starts at start, not 0, so we never pick a candidate that came before the current one in the sorted order. This guarantees no duplicate multisets. The break on line 11 exploits the sort: once sorted[i] > remaining, every subsequent candidate is even larger — safe to skip the entire tail.
Lines 13–15 — include, recurse at i, backtrack. Passing i (not i+1) is the reuse mechanism — the same candidate can appear multiple times. After the recursive call returns, path.pop() restores the path so the loop can explore the next candidate.
Complexity → Time O(nt/m) where t = target and m = minimum candidate value (max recursion depth t/m, up to n branches). Stack depth O(t/m). The sort + early-break prune dramatically cuts the constant factor in practice.

INTERVIEWFollow-ups they'll ask

  • “Combination Sum II — candidates may have duplicates, each used once?” Sort, then inside the loop skip if (i > start && candidates[i] === candidates[i-1]) continue and pass i+1 to the recursive call.
  • “Can you return the count instead of the combinations?” Yes — replace the result array with a counter and increment instead of pushing. This is equivalent to an unbounded knapsack DP: dp[j] += dp[j - c].
  • “What if target is unreachable?” The DFS simply never hits the base-case and returns an empty array — no special handling needed.
  • “What's the iterative version?” Use an explicit stack that stores (path, start, remaining) tuples. Harder to read than the recursive version; only worth it if the interviewer asks.
  • “How does this relate to coin change?”Coin Change (LC 322) is the same problem but asks for the minimum number of coins — that's unbounded knapsack DP, which runs in O(n·target) vs the backtracking's exponential cost when you only need a count or minimum.

OPTIMAL Backtracking

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

  function dfs(start: number, path: number[], remaining: number): void {
    if (remaining === 0) {
      result.push([...path]);   // found a valid combination
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break; // pruned: sorted, so all further also too large

      path.push(sorted[i]);
      dfs(i, path, remaining - sorted[i]); // i not i+1: allow reuse of same candidate
      path.pop();
    }
  }

  dfs(0, [], target);
  return result;
}
Complexity → Time O(nt/m) where t = target and m = minimum candidate value (max recursion depth t/m, up to n branches). Stack depth O(t/m). The sort + early-break prune dramatically cuts the constant factor in practice.

ALT 1 Brute force — try every candidate each step, dedup orderings

Exponential time · O(target / min) recursion depth

At every step try each candidate (reuse allowed) and recurse on the smaller remaining target. This generates the same multiset in different orders, so canonicalise by sorting each successful path and store it in a set to drop the duplicates.

approach-2.ts
function combinationSum(candidates: number[], target: number): number[][] {
  const seen = new Set<string>();
  const result: number[][] = [];

  function dfs(path: number[], remaining: number): void {
    if (remaining === 0) {
      const key = [...path].sort((a, b) => a - b).join(',');
      if (!seen.has(key)) {            // collapse permutations of the same combo
        seen.add(key);
        result.push([...path].sort((a, b) => a - b));
      }
      return;
    }
    if (remaining < 0) return;

    for (const c of candidates) {      // no 'start' index — every candidate every time
      path.push(c);
      dfs(path, remaining - c);
      path.pop();
    }
  }

  dfs([], target);
  return result;
}
Note → Allowing every candidate at every step explores all orderingsof each combination — e.g. [2,3] and [3,2] — which a set then has to deduplicate. Threading a start index (the optimal) only ever moves forward, so each combination is generated exactly once with no set needed.

MNEMONIC The one-liner

"Recurse at i to reuse, loop to i+1 to refuse — start index is the uniqueness guardian."

TRIGGERS When you see ___ → reach for ___

"combinations that sum to target, reuse allowed"backtracking DFS with start index i
"unique combinations / no duplicate sets"pass start index, never go backwards
"prune when candidate > remaining"sort + break (not continue)
"count combinations (not list)"unbounded knapsack DP — O(n·target)

SKELETON The reusable shape

skeleton.ts
function combinationSum(candidates: number[], target: number): number[][] {
  const result: number[][] = [];
  candidates.sort((a, b) => a - b);

  function dfs(start: number, path: number[], remaining: number): void {
    if (remaining === 0) { result.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break; // prune
      path.push(candidates[i]);
      dfs(i, path, remaining - candidates[i]); // reuse: i, not i+1
      path.pop();
    }
  }

  dfs(0, [], target);
  return result;
}

FLASHCARDS Tap to flip

Why pass i (not i+1) to the recursive call?
To allow reuse of the same candidate. Passing i+1 would forbid using the same number twice.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
For candidates=[2,3,6,7], target=7, what does the function return?
QUESTION 02
Why do we pass i (not i+1) in the recursive call?
QUESTION 03
What guarantees no duplicate multisets in the output?
QUESTION 04
The line if (sorted[i] > remaining) break; — why break and not continue?
QUESTION 05
Worst-case time complexity?
QUESTION 06
Combination Sum II differs from Combination Sum I in which two ways?
QUESTION 07
A candidate is added to the path and then removed after the recursive call. This “undo” step is called:
QUESTION 08
#39 · Combination SumFind all unique combinations of candidates that sum to a target, each candidate reusable. Backtracking DFS stays at index i to allow reuse and advances to i+1 to prevent duplicate sets.Which algorithmic approach does this primarily use?
QUESTION 09
#39 · Combination SumFind all unique combinations of candidates that sum to a target, each candidate reusable. Backtracking DFS stays at index i to allow reuse and advances to i+1 to prevent duplicate sets.Which implementation correctly solves it?