Backtracking Algorithms Explained

Backtracking is a technique for solving problems by building a candidate solution one piece at a time, checking after each piece whether it can still lead to a valid answer, and immediately abandoning — “backtracking” out of — any partial solution the moment it can’t. It’s a systematic way to search a large space of possibilities without exploring branches that are already provably dead ends, which is what separates it from naive brute force.

The core pattern

Every backtracking algorithm follows the same shape: choose a candidate for the next piece of the solution, check whether it’s still valid given everything chosen so far, recurse into the rest of the problem if it is, and undo the choice to try the next candidate if the recursive call fails or the branch is exhausted.

def backtrack(partial_solution):
    if is_complete(partial_solution):
        record(partial_solution)
        return
    for candidate in next_candidates(partial_solution):
        if is_valid(partial_solution, candidate):
            partial_solution.append(candidate)
            backtrack(partial_solution)
            partial_solution.pop()  # undo — this is the "back" in backtracking

That pop() after the recursive call is the entire idea in one line: try a choice, explore everything downstream of it, then remove it and try the next option as if it had never happened. Because the check happens as early as possible — before fully building out a doomed branch — backtracking prunes large parts of the search space that pure brute force would waste time exploring to completion.

Backtracking vs brute force

Brute force generates every possible complete solution and checks each one at the end. Backtracking checks validity incrementally, at every partial step, and stops extending a branch the moment it’s clearly invalid. For a problem like placing eight queens on a chessboard so none attacks another, brute force would generate and check all possible placements of eight queens across sixty-four squares; backtracking places one queen per row and immediately abandons a row’s placement the instant it conflicts with a previously placed queen, never wasting time filling out the remaining rows of a board that’s already broken.

Classic examples

N-Queens. Place queens one row at a time. Before placing a queen in a column, check it doesn’t share a column or diagonal with any queen already placed. If no column works for the current row, backtrack to the previous row and try its next option.

Sudoku solving. Fill cells one at a time in some fixed order. Before placing a digit, check it doesn’t already appear in the same row, column, or 3×3 box. If a cell has no valid digit, backtrack to the previous cell and try its next candidate.

Generating permutations or subsets. Build a sequence by repeatedly choosing an unused element; backtrack once all elements at the current position have been tried. Since every partial sequence is automatically valid (there’s no constraint to violate), this is really a plain recursive enumeration — pure backtracking’s pruning shows its value specifically on problems that do have constraints to check.

Maze and pathfinding. Move one step at a time through a grid, marking visited cells, and backtrack when a path dead-ends. This is close in spirit to depth-first search, and in fact backtracking is essentially DFS over the tree of partial solutions rather than over a fixed graph.

Backtracking vs dynamic programming

Both techniques break a problem into smaller decisions, but they diverge on what to do with those decisions. Dynamic programming is worth reaching for when subproblems overlap — the same smaller decision recurs across multiple branches — because it caches each subproblem’s result instead of recomputing it. Backtracking is the right tool when the problem is a search over combinatorial choices with hard constraints to satisfy, and subproblems generally don’t repeat in a way that’s worth caching. The two aren’t mutually exclusive: some problems benefit from backtracking with memoization layered on top, once the search structure reveals which partial states recur. For a fuller comparison of when each style of decomposition pays off, see greedy algorithms vs dynamic programming.

Why pruning early matters

The value of backtracking comes almost entirely from how early it can detect a dead end. A backtracking Sudoku solver that only checks validity after filling the entire board offers no advantage over brute force — the pruning has to happen at each step, not just at the end, or the “back” in backtracking never actually triggers before wasted work has already been done. This is why the specific order candidates are tried in, and how tight the validity check is, has an outsized effect on real-world performance even though the worst-case time complexity of many backtracking algorithms remains exponential regardless of ordering — a tighter, earlier check reduces how much of that exponential space actually gets visited in practice.

The takeaway

Backtracking builds a solution incrementally, validating each partial step and abandoning any branch that’s already invalid before wasting time completing it. It’s the standard approach for constraint-satisfaction problems like N-Queens and Sudoku, and it’s really depth-first search applied to a tree of partial solutions. The technique’s entire performance advantage over brute force comes from pruning early and often — the earlier a dead branch is detected, the less of the exponential search space it costs to rule out.