Combination Sum

BACKTRACKING · MEDIUM

Builds on Day 9: Recursion & the Call Stack

Both solutions below are recursive backtracking; read that lesson first if the call stack mental model is still new.

The problem

Given an array of distinct positive integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one chosen number differs.

Solution 1: Brute force — explore every branch, check afterward

At each step, try every remaining candidate (allowing reuse), recurse regardless of whether the running sum has already gone too high, and only check whether the target was hit after descending. This wastes time exploring branches that could have been ruled out immediately.

Flow diagram

Brute force: try any candidate, check remain only after descending
    ↓
try candidates[i]  →  recurse one level deeper  →  check remain now
(no check before      (remain -= candidates[i])    (0 = valid,
 recursing)                                        <0 = wasted branch)

Cost: many branches get fully explored before being discarded.

Interactive visualization

Brute force: candidates=[2,3], target=5 — explores every branch, even past target

Press Play or Step to begin.

call stack depth: 0

Step 0 / 0

▶ PlayStep ⏭⟲ Reset

The code

function combinationSumBrute(candidates, target) {
  const result = [];
  function dfs(start, remain, path) {
    if (remain === 0) { result.push(path.slice()); return; }
    if (remain < 0) return;
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      dfs(i, remain - candidates[i], path);
      path.pop();
    }
  }
  dfs(0, target, []);
  return result;
}

Line by line:

• dfs(start, remain, path) tracks which index is still allowed to be reused from (start, since numbers can repeat) and how much of the target is still unassigned (remain).
• remain === 0 is a complete valid combination — record a COPY of path via .slice() (not the live array, which keeps mutating as the recursion continues).
• remain < 0 means this branch already overshot — but notice the candidate was already pushed and a full recursive call already happened before this gets caught.
• The loop always tries every remaining candidate, with no check on whether candidates[i] alone could possibly still fit.

Complexity

Branches explored	Recursion depth
Every branch, even past target	O(target / min(candidates))

Solution 2: Optimal — sort + prune before recursing

Sort candidates first. Once a candidate is bigger than what’s left to reach the target, every later candidate (sorted ascending) is guaranteed too big as well — break the loop immediately instead of wasting a recursive call finding that out.

Flow diagram

Optimal: sort ascending, prune before recursing
    ↓
sort ascending  →  candidates[i] > remain?  →  break — no recursion
(once, up front)   (check BEFORE recursing)    (every later one is bigger too)

Cost: invalid branches never get a stack frame at all.

Interactive visualization

Optimal: candidates=[2,3], target=5 — sorted + pruned before recursing

Press Play or Step to begin.

call stack depth: 0

Step 0 / 0

▶ PlayStep ⏭⟲ Reset

The code

function combinationSumOptimal(candidates, target) {
  const sorted = candidates.slice().sort((a, b) => a - b);
  const result = [];
  function dfs(start, remain, path) {
    if (remain === 0) { result.push(path.slice()); return; }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remain) break;
      path.push(sorted[i]);
      dfs(i, remain - sorted[i], path);
      path.pop();
    }
  }
  dfs(0, target, []);
  return result;
}

Line by line:

• Sorting once up front is what makes the break safe — without sorting, a later candidate might still be small enough even if the current one wasn’t.
• if (sorted[i] > remain) break is the entire optimization: skip the recursive call (and the pop that would’ve undone it) for every remaining candidate in this loop, not just this one.
• remain === 0 still ends a valid path — nothing about the base case changed, only how many invalid branches get explored on the way there.

Complexity

Branches explored	Recursion depth
Prunes overshooting branches before recursing	O(target / min(candidates))

Complexity comparison

Solution	Branches explored
Brute force	Every branch, even past target
Optimal	Prunes overshooting branches before recursing

Both share the same worst-case complexity class — this is a search problem, not one with a different asymptotic solution — but the optimal version prunes dramatically better in practice by cutting off entire invalid subtrees before recursing into them, instead of discovering they’re invalid one level too late.

Interview corner

Why is path.slice() needed when recording each result?

• path is the SAME array object mutated throughout the whole recursion (pushed and popped repeatedly).
• Pushing the live reference into result would mean every recorded answer ends up reflecting path’s state whenever the WHOLE recursion finishes, not its state at that specific moment.
• .slice() makes an independent snapshot, so each result stays frozen at exactly the combination it represented.

How would you extend this to Combination Sum II, where candidates may contain duplicates and each number can only be used once?

• Sort the candidates first (needed for both correctness and duplicate-skipping).
• Advance the start index by i + 1 (not i) in the recursive call, since each number is now used at most once.
• Skip over a duplicate value at the same recursion depth (if (candidates[i] === candidates[i-1] && i > start) continue) to avoid generating the same combination twice.

What’s the maximum possible recursion depth for this problem?

• Bounded by target / min(candidates) — you can never place more candidates than that before overshooting the target.
• This bounds both the call stack depth and the path array’s length.

Trick question — what does this log?

const result = [];
function dfs(path) {
  if (path.length === 2) { result.push(path); return; }
  path.push(1);
  dfs(path);
  path.pop();
}
dfs([]);
console.log(JSON.stringify(result));

• Answer: [[]], not [[1,1]].
• path is the same mutable array reused throughout the recursion.
• By the time the recursion fully unwinds (every path.pop() has run), the array that was pushed into result has been mutated back down to empty.
• ⚠ Trap: this is exactly the bug the real Combination Sum solution above avoids by using path.slice() instead of pushing path directly.

Quiz

Quiz: 1. Why can the same candidate be reused multiple times in one combination?

dfs(i, …) passes the SAME index i (not i+1) as the next start index, keeping the current candidate eligible again

dfs(i, …) passes the SAME index i (not i+1) as the next start index, keeping the current candidate eligible again on the next recursive call — that’s what allows unlimited reuse.

Quiz: 2. What’s the purpose of the remain < 0 check in the brute-force solution?

It detects an overshoot AFTER already recursing one level too deep — the branch is invalid but wasn’t caught before the wasted call

remain < 0 catches an overshoot, but only AFTER a candidate was already pushed and a full recursive call already happened — the branch was invalid the whole time, it just wasn’t caught before the wasted call.

Quiz: 3. Why does sorting first make the break in the optimal solution safe?

Once one candidate is too big, every later candidate (ascending order) is guaranteed too big as well

Because the array is sorted ascending, once one candidate exceeds remain, every candidate after it in the loop is guaranteed to be at least as large — so breaking out of the loop entirely is safe, not just skipping that one candidate.

Quiz: 4. Why must path.slice() be used when recording a result, instead of pushing path directly?

path is the same mutable array reused throughout the recursion — pushing the live reference would record its FINAL state, not its state when the combination was found

path is the same mutable array reused throughout the recursion — every push and pop happens on that one object. Pushing the live reference would record whatever path looks like once the ENTIRE recursion finishes, not the moment the combination was found. .slice() takes an independent snapshot.

Quiz: 5. What’s the key difference in branches explored between the two solutions, given they share the same worst-case complexity class?

The optimal solution prunes overshooting branches BEFORE recursing into them, so its practical branch count is much smaller

Both solutions share the same worst-case Big-O — sorting and pruning doesn’t change the asymptotic class. What changes is practical branch count: the optimal version cuts off invalid subtrees before recursing into them at all, instead of discovering they’re invalid one level too late.