Learn how backtracking systematically explores all possibilities by building candidates and abandoning paths that cannot lead to a solution.

Backtracking

Backtracking is a recursive technique for exploring all possible solutions to a problem. It builds candidates incrementally — one choice at a time — and backtracks (undoes the last choice) as soon as it determines that the current path cannot lead to a valid solution.

Think of it like navigating a maze. You walk forward until you hit a dead end, then retrace your steps to the last fork and try a different direction. You keep doing this until you either find the exit or exhaust all paths.

Backtrackingall subsets of [1, 2, 3]

0 subsets found

current subset

[empty ∅]

input nums

recursion depth:

subsets collected

none yet

subsets_backtrack.py

def backtrack(start, current):

result.append(current[:]) # record

for i in range(start, n):

current.append(nums[i])

backtrack(i + 1, current)

current.pop() # ← backtrack

Generate all subsets of [1, 2, 3] using backtracking

step 0/23

The general pattern

Every backtracking solution follows the same three-step structure:

def backtrack(state, choices):
    # 1. base case — found a complete solution
    if is_solution(state):
        record(state)
        return

    for choice in choices:
        # 2. make a choice
        if is_valid(state, choice):
            state.add(choice)

            # 3. recurse with the new state
            backtrack(state, remaining_choices)

            # 4. undo the choice (backtrack)
            state.remove(choice)

The key — undo the choice after the recursive call returns. This restores the state so the next choice starts from the same clean slate.

Example — generate all subsets

def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(current[:])   # record this subset

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

    backtrack(0, [])
    return result


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

Example — generate all permutations

def permutations(nums):
    result = []

    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return

        for i, num in enumerate(remaining):
            current.append(num)
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()

    backtrack([], nums)
    return result


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

Example — N-Queens

Place N queens on an N×N chessboard so no two queens attack each other.

def n_queens(n):
    result = []
    queens = []   # queens[i] = column of queen in row i

    def is_safe(row, col):
        for r, c in enumerate(queens):
            if c == col: return False              # same column
            if abs(r - row) == abs(c - col): return False  # diagonal
        return True

    def backtrack(row):
        if row == n:
            result.append(queens[:])
            return

        for col in range(n):
            if is_safe(row, col):
                queens.append(col)       # place queen
                backtrack(row + 1)       # try next row
                queens.pop()             # remove queen (backtrack)

    backtrack(0)
    return result


solutions = n_queens(4)
print(f"Found {len(solutions)} solutions for 4-queens")
# Found 2 solutions for 4-queens

Example — word search in a grid

def word_search(board, word):
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, idx, visited):
        if idx == len(word):
            return True   # all letters matched

        if (r < 0 or r >= rows or c < 0 or c >= cols
                or (r, c) in visited
                or board[r][c] != word[idx]):
            return False

        visited.add((r, c))

        found = (backtrack(r+1, c, idx+1, visited) or
                 backtrack(r-1, c, idx+1, visited) or
                 backtrack(r, c+1, idx+1, visited) or
                 backtrack(r, c-1, idx+1, visited))

        visited.remove((r, c))   # backtrack
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0, set()):
                return True
    return False

Pruning — the key optimization

Without pruning, backtracking explores all possible paths — potentially exponential. Pruning cuts off branches early when you can determine they cannot lead to a solution:

# without pruning — tries every combination
for choice in all_choices:
    make(choice)
    backtrack()
    undo(choice)

# with pruning — skip impossible paths immediately
for choice in all_choices:
    if is_valid(choice):          # ← pruning check
        make(choice)
        backtrack()
        undo(choice)

Good pruning can reduce exponential time to something manageable in practice.

Backtracking is fundamentally brute force with early termination. The worst case is still exponential — but pruning ensures that in practice, many branches are never explored. The difference between a working backtracking solution and an unusably slow one is almost always the quality of the pruning.

Complexity

Backtracking complexity varies widely by problem. As a rough guide:

Problem	Approximate complexity
All subsets of n items	O(2ⁿ)
All permutations of n items	O(n!)
N-Queens	O(n!)
Sudoku	O(9^81) worst case, much less with pruning

Backtracking

On this page