Backtracking

Backtracking is a problem-solving pattern for exploring all possible configurations of something. You try a choice, recurse to extend it, and if it doesn't lead anywhere good — or after exploring it fully — you undo the choice and try a different one. The pattern is: try, recurse, undo.

When to Use It

Reach for backtracking when the problem asks for:

• All possible subsets, permutations, combinations, or arrangements
• A valid configuration that satisfies a set of constraints
• The best configuration measured by some score

If brute force enumeration is the only obvious approach, backtracking is usually the structured way to do it without writing nested loops by hand.

The Three-Step Pattern

Every backtracking function looks like this:

def backtrack(state):
    if is_complete(state):
        record(state)
        return
    for choice in possible_choices(state):
        if is_valid(choice, state):
            apply(choice, state)        # try
            backtrack(state)            # recurse
            undo(choice, state)         # undo

The "undo" step is what makes it backtracking instead of just brute force. Because you mutate one shared state instead of copying it, undoing is essential to keep state consistent for the next branch.

Pruning Saves the Day

Pure brute force would explore every leaf of an exponential tree. Backtracking gets fast in practice by pruning — checking constraints early and giving up on impossible branches before exploring them. In N-queens, you don't place a queen where it's already attacked. In Sudoku, you don't try a digit that violates the row, column, or box.

Canonical Examples

• Subsets: at each index, choose to include or skip
• Permutations: at each position, choose any unused element
• N-queens: place queens row by row; reject conflicts immediately
• Sudoku: fill the next empty cell with a valid digit; recurse; undo if stuck
• Word search: explore neighboring cells, marking visited; unmark on return

Try It Yourself

• Write a backtracking function that returns all combinations of k items from n
• Generate all binary strings of length n using backtracking
• Solve N-queens for n = 4 and print every valid board