Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Backtracking

Backtracking Explained

Written by Updated

Backtracking is brute force with an eraser. You try a choice, follow it, and if it leads nowhere you undo it and try the next - which is why the undo step is the part that matters.

The template

Every backtracking solution is this shape:

Choose, explore, unchoose

javascript

// A runnable instance of the template: every 2-element combination.
function backtrack(current, options, results, start) {
  if (current.length === 2) {          // a complete solution
    results.push([...current])         // copy — current keeps changing
    return
  }

  for (let i = start; i < options.length; i++) {
    current.push(options[i])                       // choose
    backtrack(current, options, results, i + 1)    // explore
    current.pop()                                  // unchoose
  }
}

const results = []
backtrack([], ["a", "b", "c"], results, 0)
console.log(results)   // [["a","b"], ["a","c"], ["b","c"]]

Two details cause most bugs: copying when you record a solution, and undoing after exploring. Miss the copy and every result is the same array. Miss the undo and choices leak into sibling branches.

Subsets

Every subset

javascript

function subsets(nums) {
  const results = []

  function build(start, current) {
    // Every state is itself a valid subset.
    results.push([...current])

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i])
      build(i + 1, current)   // i + 1, so no element repeats
      current.pop()
    }
  }

  build(0, [])
  return results
}

console.log(subsets([1, 2, 3]))
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

2^n subsets, so O(2^n × n) including the copies. That is inherent - there are that many answers.

Permutations

Every ordering

javascript

function permutations(nums) {
  const results = []
  const used = new Array(nums.length).fill(false)

  function build(current) {
    if (current.length === nums.length) {
      results.push([...current])
      return
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue

      used[i] = true
      current.push(nums[i])

      build(current)

      current.pop()      // undo both
      used[i] = false
    }
  }

  build([])
  return results
}

console.log(permutations([1, 2, 3]).length)  // 6

Note that used[i] = false is undone as well as the push. Every piece of state you change on the way down must be restored on the way up.

Pruning is the whole optimisation

Backtracking is exponential. The only way to make it fast is to abandon branches early - stop as soon as a partial solution cannot possibly work, rather than completing it and rejecting it.

Combinations summing to a target

javascript

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

  function build(start, current, remaining) {
    if (remaining === 0) {
      results.push([...current])
      return
    }

    for (let i = start; i < sorted.length; i++) {
      // Sorted, so every later candidate is bigger too — stop entirely.
      if (sorted[i] > remaining) break

      current.push(sorted[i])
      build(i, current, remaining - sorted[i])   // i, so reuse is allowed
      current.pop()
    }
  }

  build(0, [], target)
  return results
}

console.log(combinationSum([2, 3, 6, 7], 7))  // [[2,2,3], [7]]

The break is the pruning. Sorting first is what makes it valid - without a sorted list you could only continue, and you would explore far more dead ends.

The shape every backtracking problem takes

Choose, recurse, un-choose. The un-choose step is what makes it backtracking rather than plain recursion, and forgetting it is the bug you will hit first - the path keeps growing because nothing ever removes what you added.

The template

javascript

function solve(input) {
  const results = []
  const path = []

  function backtrack(start) {
    if (isComplete(path)) {
      results.push([...path])   // copy — path keeps mutating
      return
    }

    for (const choice of choicesFrom(start)) {
      if (!isValid(choice, path)) continue

      path.push(choice)         // choose
      backtrack(start + 1)      // explore
      path.pop()                // un-choose
    }
  }

  backtrack(0)
  return results
}

// The template above is a shape to copy, not something runnable on its own —
// isComplete, choicesFrom and isValid are yours to supply per problem.
console.log("template: choose, recurse, un-choose")

Note [...path] rather than path. Pushing the array itself stores a reference to something that is about to be mutated, so every result ends up identical - usually empty. This is the second bug everyone hits.

Pruning is the whole game

Unpruned backtracking explores every combination, which is exponential and hopeless past small n. The isValid check is what makes it tractable: rejecting a partial path early removes an entire subtree of work, not one candidate.

PreviousTurning Recursion Into IterationNextClassic Backtracking Problems