Backtracking Algorithm

I once spent hours debugging a scheduling system that needed to find valid combinations from a huge set of options. Nested loops weren't cutting it. What I needed was backtracking.

What It Does

Backtracking builds a solution one decision at a time. If a decision leads to a dead end, it undoes that decision and tries a different one. Think of it like exploring a maze — you walk forward until you hit a wall, then retrace your steps and try another path.

It's brute force, but smarter. You prune entire branches of the search tree the moment you know they can't lead to a valid answer.

The Pattern

Every backtracking solution follows the same skeleton:

1. Choose — pick a candidate.
2. Check — does it violate any constraints?
3. Recurse — move to the next decision.
4. Undo — if it didn't work, remove the candidate and try the next one.

Example: Combination Sum

Find all combinations of numbers from candidates that add up to target. You can reuse numbers.

function combinationSum(candidates, target) {
  const results = [];

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

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

  backtrack(0, [], target);
  return results;
}

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

Complexity

• Time: O(n^(t/m)) where n is the number of candidates, t is the target, and m is the smallest candidate. Exponential in the worst case.
• Space: O(t/m) for the recursion depth.

When to Use It

Backtracking is your tool when:

• You need to find all valid solutions (not just one).
• The problem has constraints that let you prune early.
• The search space is too large for brute force but structured enough for pruning.

Classic problems: N-Queens, Sudoku, permutations, subset sum, graph coloring.

The Trade-off

Backtracking is easy to reason about and implement. But it's still exponential at its core. For problems where you see overlapping subproblems, dynamic programming will be faster. For optimization problems, greedy might be enough. Backtracking shines when you need exhaustive search with pruning.