What is Backtracking?

The core idea: choose, explore, undo

Imagine walking a maze while unspooling a thread. At each junction you pick a direction and keep going. When you hit a wall, you follow the thread back to the last junction and try a different direction. Backtracking is that thread-and-junction idea turned into code: make a choice, recurse to explore its consequences, and if that path fails, undo the choice and try the next one.

What makes it more than blind trial and error is that you abandon a path the instant it is provably hopeless, not only when it is fully complete. If placing a queen already puts two queens on the same diagonal, there is no point filling the rest of the board, so you undo and move on. That early abandonment is the whole point.

How it works: the state-space tree and pruning

Formally, backtracking performs a depth-first search over a state-space tree. Each node is a partial solution and each edge is one additional choice: the next number in a permutation, the next queen's column, the next digit in a Sudoku cell. A recursive function tries every valid choice at the current level, and after each recursive call it restores state so the next choice starts clean. When the partial solution is complete you record it; when no choice is valid the call simply returns and control flows back up the tree.

Two moves define every backtracking function: the constraint check (is this choice still valid?) and the undo (remove the choice before trying the next). The constraint check is where pruning happens, and the tighter and earlier it is, the more of the tree you skip. This is exactly the kind of process that clicks once you watch it animate: you can see the recursion dive down a branch, hit a violated constraint, and retreat one level to try the next option.

One template, many problems

Almost every backtracking solution fits the same shape: a base case that records a completed solution, a loop over candidate choices, and a choose / recurse / undo trio inside that loop. Learn that skeleton once and permutations, subsets, combination sum, N-Queens, word search, and Sudoku all become variations on where you get the candidates and how you check validity.

The differences are mostly in candidate generation. For subsets you decide include-or-skip on each element; for permutations you pick any unused element; for grid problems you branch into neighboring cells. The recursion, the base case, and the undo stay recognizably the same.

The code

def permutations(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:               # complete solution
            result.append(path[:])      # store a COPY, not the shared list
            return
        for i in range(len(remaining)):
            path.append(remaining[i])                        # choose
            backtrack(path, remaining[:i] + remaining[i + 1:])  # explore
            path.pop()                                       # undo

    backtrack([], nums)
    return result

Run it in the browser IDE, free on the platform. Open the IDE →

Complexity

Backtracking's cost is the number of nodes it visits in the state-space tree, so it is problem-dependent: subsets are O(2^n), N-Queens is roughly O(n!). Strong pruning (constraint checks that fail early) massively cuts the real work but does not change the Big-O worst case.