The first time I tried to solve the N-Queens problem, I wrote something that was technically recursive but completely wrong. It didn't backtrack — it just blundered forward, placed queens wherever, and never undid bad decisions. My output was a board where queens attacked each other confidently.

That's the thing about backtracking: it requires you to be willing to undo your work. And for some reason, that feels unnatural at first. Let's fix that.

Recursion First

Recursion is solving a problem by breaking it into smaller versions of itself. The key ingredients: a base case (the simplest version of the problem, solved directly) and a recursive case (how you reduce the problem toward the base case).

The call stack does the bookkeeping. Each recursive call gets its own frame with its own local variables, and when it returns, execution continues from where it left off in the caller. Visualizing this stack is crucial — if you're fuzzy on what "the call stack" means, trace through a factorial or Fibonacci calculation manually and watch the frames stack up and unwind.

Backtracking = Recursion + Undoing Choices

Backtracking explores decision trees. At each step, you make a choice, recurse to explore that branch, and then undo the choice before trying the next one. The "undo" step is what distinguishes backtracking from regular recursion.


function backtrack(state, choices) {
  if (isComplete(state)) {
    recordSolution(state);
    return;
  }

  for (const choice of choices) {
    if (isValid(state, choice)) {
      makeChoice(state, choice);         // modify state
      backtrack(state, nextChoices(...));  // recurse
      undoChoice(state, choice);          // restore state  ← the backtrack
    }
  }
}

The crucial thing: state must be fully restored before the next iteration of the loop. If you forget the undo step, choices from one branch contaminate the next branch. This is the most common backtracking bug.

A Concrete Example: Generating All Permutations

Given [1, 2, 3], generate all 6 permutations.

State: the current permutation being built. Choices at each step: whichever numbers haven't been used yet. Base case: permutation length equals input length.

The decision tree has 3 branches at the root (pick 1, 2, or 3 first), 2 branches at the next level, and 1 at the last. 3 × 2 × 1 = 6 leaves. Each leaf is a complete permutation. Backtracking visits every leaf and the total work is O(n × n!) — n to copy each solution, n! solutions.

Pruning: Where Backtracking Gets Smart

The isValid check in the template is where you add pruning. In N-Queens, before placing a queen, check if the position is attacked. If it is, skip that branch entirely — don't recurse into it. Pruning can reduce the explored tree from exponential to something manageable in practice, even if the worst case is still exponential.

Sudoku solvers use aggressive constraint propagation as pruning: after placing a number, immediately eliminate that number from all peers in the same row, column, and box. This often forces subsequent cells without any backtracking needed.

Common Backtracking Problems to Practice

Work through these in roughly this order — each one adds a layer of complexity:

Subsets (easiest — just binary choices at each element)
Permutations (all orderings, track used elements)
Combination Sum (with duplicates and target sums)
Word Search on a grid (2D backtracking)
N-Queens (constraint checking while placing)
Sudoku Solver (the full package)

After Sudoku, almost no backtracking problem will feel unfamiliar structurally. The patterns are the same — the domain just changes.

One Last Thing

Backtracking is inherently exponential in the worst case. That's usually fine because pruning reduces the actual work dramatically, and the problems it solves (constraint satisfaction, enumeration) often don't have polynomial solutions anyway. Don't reach for backtracking when a greedy or DP solution exists — but when you need to explore a decision space, it's the right tool.

Recursion and Backtracking: A Visual Walkthrough