Backtracking: Choose, Explore, Unchoose

Backtracking is recursion with regret. You make a choice, go deep, and if it doesn't work out, you undo the choice and try something else. That's really all it is.

The pattern is dead simple:

1. Choose — pick an option from the available candidates
2. Explore — recurse with that choice made
3. Unchoose — remove the choice (backtrack) and try the next candidate

def backtrack(state, choices):
    if is_solution(state):
        result.append(state.copy())
        return
    for choice in choices:
        if is_valid(choice, state):
            state.add(choice)          # choose
            backtrack(state, choices)   # explore
            state.remove(choice)        # unchoose

That template covers a surprising number of problems.

N-Queens: The Classic

Place N queens on an N x N chessboard so no two queens attack each other. No shared rows, columns, or diagonals.

The brute force approach would try every possible arrangement of N queens on N^2 squares. That's absurd. Backtracking is smarter: place queens one row at a time. For each row, try each column. If placing a queen there conflicts with an existing queen, skip it (prune). If you get through all N rows, you've found a solution.

def solve_queens(n):
    result = []

def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # pruning — this is what makes it not brute force
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

backtrack(row + 1, cols, diag1, diag2, board)

board[row][col] = '.'  # unchoose
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return result

The diagonal trick: two squares share a diagonal if row - col is equal (one direction) or row + col is equal (other direction). Using sets for columns and both diagonal directions gives O(1) conflict checking.

The Big Three: Subsets, Permutations, Combinations

These three problems are the backtracking fundamentals. Almost everything else is a variation.

Subsets

Generate all subsets of a set. For each element, you have two choices: include it or don't.

def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

2^n subsets, so O(2^n) time. There's no way around it — you're generating all of them.

Permutations

All orderings of a set. Each position can hold any unused element.

def permutations(nums):
    result = []
    def backtrack(current, used):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if i in used:
                continue
            used.add(i)
            current.append(nums[i])
            backtrack(current, used)
            current.pop()
            used.remove(i)
    backtrack([], set())
    return result

n! permutations. Grows fast, but that's inherent to the problem.

Combination Sum

Find all combinations that sum to a target, where elements can be reused.

def combination_sum(candidates, target):
    result = []
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        if remaining < 0:
            return  # prune
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])
            current.pop()
    backtrack(0, [], target)
    return result

The start parameter prevents duplicates — you never go backwards in the candidates list. The remaining < 0 check is pruning that avoids exploring branches that have already exceeded the target.

Backtracking vs Brute Force

Brute force generates every possible candidate and checks each one. Backtracking generates candidates incrementally and abandons a partial candidate as soon as it determines the candidate can't lead to a valid solution.

The difference is pruning. In N-Queens, brute force tries all N^N placements. Backtracking prunes entire subtrees the moment a conflict is detected. For N=8, brute force considers ~16 million placements. Backtracking explores around 15,000 nodes. That's three orders of magnitude difference, and the gap grows with N.

Pruning effectiveness varies by problem. Good pruning conditions can turn an otherwise intractable problem into something solvable. Bad or missing pruning means your "backtracking" solution is just brute force with extra steps.

When to Use Backtracking vs DP vs Greedy

Backtracking when you need to enumerate all solutions or find any valid solution to a constraint satisfaction problem. Subsets, permutations, board configurations, valid parentheses, Sudoku solving. DP when you need the optimal value (not all solutions) and the problem has overlapping subproblems. Backtracking with memoization literally becomes DP, which is why the boundary is fuzzy. Greedy when the locally optimal choice is provably globally optimal. Much faster, but only works for specific problem structures.

The decision tree: Can greedy solve it? Use greedy. Need optimal value with overlapping subproblems? Use DP. Need all valid configurations or any valid configuration? Backtracking.

On Exponential Time Complexity

Yes, backtracking is usually O(2^n) or O(n!). That sounds bad, and it is — for large n. But the problems that require backtracking typically have small input sizes. N-Queens with N=12 is already a challenge problem. Sudoku is always 9x9. Subsets of a 20-element set is 2^20 = ~1 million, which finishes in milliseconds.

The exponential complexity is a feature of the problem, not a flaw in the algorithm. You can't enumerate all subsets of a set faster than O(2^n) because there are 2^n subsets. Backtracking just does it without wasting time on branches that can't work.

If you want to get comfortable with the choose-explore-unchoose pattern, CodeUp has a progression of backtracking problems that start with basic subsets and build up to constraint-heavy puzzles — the kind of practice that makes the template second nature.