Introduction to Backtracking

Imagine trying write a program which places eight queens on a chessboard so none of them attack each other, or say fill in a Sudoku grid. None of these problems have an easy solution just using loops.

When you can't brute force

The obvious plan is to generate every possible arrangement, then throw out the ones that break the rules.

For problems like the classic N-queens LeetCode problem, choosing 8 squares out of 64 gives you a little over 4.4 billion arrangements to check, and most importantly most of these arrangements are obviously wrong and just a waste of time to check.

Instead of brute forcing all configurations, we can start with one queen, then try out all possible legal configurations for two queens, then three, and so on. Two queens in the same row always attack each other, so any real solution has exactly one queen per row. So instead of choosing squares, choose a column for each of the 8 rows. That's 8 to the power of 8, about 16.7 million, still huge, but nearly three hundred times smaller.

That last row is the way a backtracking style solution would solve the N-queens problem.

Wait, it's all a tree?

Since it's impossible to check all possible answers, backtracking uses a tree to check all possible legal boards step by step.

Every edge going down is a possible legal move, and every node is the partial answer you've built so far. It follows then that this tree has all possible legal board configurations, since we failed early.

The formula

Backtracking seems complicated, but every single backtracking algorithm has the same structure.

We start by checking if we are at the leaf i.e., the bottom of the tree, for the N-queens example this would mean we already have 8 queens down. If so, we record our answers, then we exit (because its the end of that specific path.

After that, we recursively run the backtracking function, for the first legal move, undo, then run it for the second legal move, undo, then run it for the third legal move, etc. Remember, we undo because we want to check out every single possible branch of our tree. This is the exact same pattern for Depth-First Search (DFS), it checks it branch by branch going as deep as possible.

def solve(state):
    if state.property == complete:
        # record
        return

    for choice in available_choices:
        if not legal(choice):
            continue # fail early
        
        apply(choice) # usually change in state
        solve(state)
        undo(choice)

The continue right above it is the prune, essentially optimizing our algorithm by only making moves that are "legal".

Watch the tree get built

This is the same template on a problem where the rules do reject candidates: combination sum, hunting for numbers from a fixed list that add up to a target. Flip pruning on and off and watch the two counters below the tree. Cutting overshooting branches early is the entire difference between them.

Time complexity

Even though backtracking is relatively efficient, it's still usually really slow and often runs in exponential time. Subsets of n items really does produce some base to the power of n answers, and no algorithm can list them faster than it can print them. Permutations really do number n factorial. When the answer itself is exponentially large, the algorithm has to be too.

Memory's the reassuring part. At any moment you're only holding one root-to-leaf path, so the space you use is proportional to the depth of the tree, not its size. A search that visits billions of nodes might only ever hold a few dozen items.

Common Mistakes

Forgetting to undo.

for (let i = start; i < nums.length; i++) {
  current.push(nums[i]);
  solve(i + 1);
  // current.pop();   <-- forgotten
}

Storing the working list itself instead of a copy of it is almost as common a mistake, and way more confusing, because the code looks completely right.

answers.push(current);      // WRONG: stores a reference
answers.push([...current]); // right: stores a snapshot

That first line pushes a reference to the one list you keep editing. Since it ends empty, every answer you thought you collected turns out empty too, and the bug looks like it's coming from nowhere. Take a snapshot the moment you record.

Checking the rules only at the leaves. Totally correct, and it quietly throws away every advantage backtracking gives you. If your solver works but is way too slow, this is the first thing to check: are you actually validating as early as you possibly could?

Pruning something that was actually valid. The opposite failure, and the harder one to catch, because the program runs fast and just quietly misses answers. If your solver returns 88 solutions to eight queens instead of 92, the prune is too aggressive, not the search itself.

In code

Here's subsets written out. Compare it against the template above, line by line, and you'll find every piece of it in there, including the start parameter, which exists so a choice you already considered doesn't get offered again further down.

function subsets(nums) {
  const answers = [];
  const current = [];

  function solve(start) {
    answers.push([...current]);        // a copy, see the note below

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);           // choose
      solve(i + 1);                    // explore
      current.pop();                   // un-choose
    }
  }

  solve(0);
  return answers;
}

From here, the rest of the section only changes what goes in the blanks. Permutations swaps the start parameter for a used-marker. N-Queens adds a real prune. Sudoku adds a rule about which blank to fill next. The skeleton never moves.

Check yourself

Take home