Backtracking Algorithms

The Maze

You're standing at the entrance of a maze. You choose a path and start walking. You go left, then right, then left again — moving forward with confidence until you hit a dead end: a wall.

What do you do? You don't give up and go back to the entrance. You back up to the last intersection — the last point where you had a choice — and try the next available direction. If that also fails, you back up further. You continue this process until you either find the exit or exhaust every possibility.

This strategy is called backtracking. It's not random guessing. It's systematic trial-and-error — exploring every possible path, but intelligently retreating the moment a path is proven wrong, instead of wasting time exploring a dead end further.

What Is Backtracking?

Backtracking = Recursion + the ability to undo choices

Standard recursion dives deeper and deeper. Backtracking dives deep, but when it discovers a dead end, it unwinds to the last decision point, reverses the choice it made there, and tries the next option.

This makes backtracking the standard tool for:

• Constraint satisfaction problems (N-Queens, Sudoku)
• Combinatorial generation (all permutations, all subsets)
• Puzzle solving (crosswords, mazes)
• Game playing (chess move generation)

The Universal Backtracking Template

Every backtracking algorithm follows the same skeleton:

def backtrack(state, choices):
    # Base case: we've built a complete solution
    if is_solution(state):
        record_solution(state)
        return

    for choice in choices:
        if is_valid(choice, state):
            make_choice(choice, state)           # Step forward
            backtrack(state, remaining_choices)  # Explore deeper
            undo_choice(choice, state)           # BACKTRACK — undo

The critical line is undo_choice — this is what makes backtracking different from plain recursion. After exploring a branch, we restore the state as if we never made that choice, so the next iteration starts from a clean slate.

Problem 1: Generating All Subsets

Given a set [1, 2, 3], generate every possible subset.

def subsets(nums):
    result = []

    def backtrack(start, current):
        # Every state is a valid subset (including empty)
        result.append(list(current))

        for i in range(start, len(nums)):
            current.append(nums[i])          # make choice: include nums[i]
            backtrack(i + 1, current)         # explore with nums[i] included
            current.pop()                     # undo choice: remove nums[i]

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))

Output:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Exploration tree:

[]
├── [1]
│   ├── [1,2]
│   │   └── [1,2,3]
│   └── [1,3]
├── [2]
│   └── [2,3]
└── [3]

Problem 2: Generating All Permutations

def permutations(nums):
    result = []

    def backtrack(current, remaining):
        if not remaining:               # base case: nothing left to add
            result.append(list(current))
            return

        for i in range(len(remaining)):
            current.append(remaining[i])                # make choice
            backtrack(current, remaining[:i] + remaining[i+1:])  # recurse
            current.pop()                               # undo choice

    backtrack([], nums)
    return result

print(permutations([1, 2, 3]))

Output:

[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

For n elements, there are exactly n! permutations. For n=10, that's 3,628,800 permutations.

Problem 3: The N-Queens Problem

The problem: Place N queens on an N×N chessboard so that no two queens attack each other. Queens attack horizontally, vertically, and diagonally.

This is the classic backtracking interview problem.

def solve_n_queens(n):
    solutions = []
    board = [-1] * n        # board[row] = column where queen is placed

    def is_safe(row, col):
        for prev_row in range(row):
            prev_col = board[prev_row]
            # Check same column
            if prev_col == col:
                return False
            # Check diagonal (|row difference| == |col difference|)
            if abs(prev_row - row) == abs(prev_col - col):
                return False
        return True

    def backtrack(row):
        if row == n:                            # all queens placed
            solutions.append(board[:])          # record this solution
            return

        for col in range(n):
            if is_safe(row, col):
                board[row] = col               # place queen
                backtrack(row + 1)             # try next row
                board[row] = -1               # remove queen (backtrack)

    backtrack(0)
    return solutions

solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions for 4-Queens")
for sol in solutions:
    print(sol)

Output:

Found 2 solutions for 4-Queens
[1, 3, 0, 2]
[2, 0, 3, 1]

Visualizing solution [1, 3, 0, 2] (column index of queen in each row):

     Col: 0  1  2  3
Row 0:  [  .  Q  .  . ]
Row 1:  [  .  .  .  Q ]
Row 2:  [  Q  .  .  . ]
Row 3:  [  .  .  Q  . ]

No two queens share a row, column, or diagonal. Valid!

N-Queens solutions by board size:

Pruning: Making Backtracking Faster

The real power of backtracking is pruning — detecting a dead end early and cutting off entire branches of the search tree.

In N-Queens, when we call is_safe(row, col) before placing a queen, we're pruning. If a column is already occupied, we don't bother placing the queen, exploring that branch, and then backing out. We skip it entirely.

Without pruning: check all N^N combinations With pruning: check far fewer — the algorithm "knows" a branch is invalid before going deeper

Without pruning (brute force N=8):
  8^8 = 16,777,216 combinations to check

With backtracking + pruning (N=8):
  ~15,720 nodes explored  ← 1000x fewer!

Backtracking explores only the necessary portion of the search space.

Time Complexity of Backtracking

Backtracking is exponential in the worst case but often much faster in practice due to pruning.

When asked about time complexity in interviews, state: "exponential worst case, but pruning makes it practical for typical inputs."

Key Takeaways

• Backtracking is recursion + state undo — try a choice, explore, then reverse it
• The template: make choice → recurse → undo choice
• Classic problems: N-Queens, subsets, permutations, Sudoku, word search
• Pruning is what makes backtracking practical — cutting invalid branches early
• Worst-case complexity is exponential, but pruning reduces actual runtime dramatically
• In interviews: trace through the decision tree, and always articulate what your is_valid check prunes

Next lesson: Bubble Sort and Selection Sort — our first concrete sorting algorithms.