Topic · BacktrackingMedium ~30 min to read and practice

Combination Sum

Understand the problem

Given an array of distinct positive integers candidates and an integer target. Find all unique combinations whose sum equals target. Each number in candidates can be used any number of times (unlimited).

Example:

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

candidates = [2, 3, 5], target = 8
output = [[2,2,2,2], [2,3,3], [3,5]]

Key point: since each number can be reused, don't advance start when recursing (stay at the current index).

Only advance start when moving on to the next number — this avoids generating duplicate combinations in a different order.

Basic approachO(n^(T/M)) time — n numbers in candidates, T is the target, M is the smallest value

// Backtracking without pruning — tries every possibility
// Backtracking is already optimal for this problem;
// the "brute force" here just lacks early termination:
function combinationSumNoPrune(
  candidates: number[],
  target: number
): number[][] {
  const result: number[][] = []

  function backtrack(start: number, current: number[], remaining: number) {
    if (remaining === 0) {
      result.push([...current])
      return
    }
    if (remaining < 0) return  // still has a stop condition, but no sort beforehand

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

  backtrack(0, [], target)
  return result
}

Why this approach is slow:

Without sorting candidates, you can't prune early when candidates[i] > remaining.

Sorting + break once a value exceeds the target greatly reduces the number of wasted branches.

Unlock the optimal solution, the step-by-step trace and related questions

See the full step-by-step trace, Big-O and edge cases.

Unlock Pro See Lifetime

Understand the problem

Example:

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

candidates = [2, 3, 5], target = 8
output = [[2,2,2,2], [2,3,3], [3,5]]

Key point: since each number can be reused, don't advance start when recursing (stay at the current index).

Only advance start when moving on to the next number — this avoids generating duplicate combinations in a different order.

// Backtracking without pruning — tries every possibility // Backtracking is already optimal for this problem; // the "brute force" here just lacks early termination: function combinationSumNoPrune( candidates: number[], target: number ): number[][] { const result: number[][] = [] function backtrack(start: number, current: number[], remaining: number) { if (remaining === 0) { result.push([...current]) return } if (remaining < 0) return // still has a stop condition, but no sort beforehand for (let i = start; i < candidates.length; i++) { current.push(candidates[i]) backtrack(i, current, remaining - candidates[i]) current.pop() } } backtrack(0, [], target) return result }