Backtracking Algorithms — Core Concepts

Why backtracking matters

Backtracking is the algorithmic framework for solving constraint satisfaction problems. Any time you need to find all valid configurations, generate combinations, or solve puzzles with rules, backtracking is your go-to approach. It powers Sudoku solvers, chess engines, compiler parsers, and even package dependency resolvers.

The backtracking template

Every backtracking algorithm follows this pattern:

def backtrack(state, choices):
    if is_solution(state):
        record(state)
        return
    
    for choice in choices:
        if is_valid(state, choice):
            make_choice(state, choice)
            backtrack(state, remaining_choices)
            undo_choice(state, choice)  # backtrack

The three critical steps:

1. Choose — pick an option to try.
2. Explore — recurse with the updated state.
3. Un-choose — undo the option and try the next one.

Generating all permutations

Given [1, 2, 3], generate all orderings:

def permutations(nums):
    result = []
    
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()  # undo
    
    backtrack([], nums)
    return result

# Returns: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Time complexity: O(n × n!) — n! permutations, each taking O(n) to record.

Generating all subsets

Generate every possible subset of [1, 2, 3]:

def subsets(nums):
    result = []
    
    def backtrack(start, path):
        result.append(path[:])  # every state is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

# Returns: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

The start parameter prevents generating duplicate subsets by only considering elements after the current position.

Combination sum

Find all combinations of numbers that sum to a target:

def combination_sum(candidates, target):
    result = []
    candidates.sort()
    
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # pruning: no point trying larger numbers
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, not i+1: reuse allowed
            path.pop()
    
    backtrack(0, [], target)
    return result

The break statement is pruning — cutting off branches that cannot lead to a solution. This is what makes backtracking efficient.

N-Queens problem

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

def solve_n_queens(n):
    solutions = []
    
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            solutions.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 position is under attack
            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] = "."
            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 solutions

Using sets for columns and diagonals gives O(1) conflict checking. The two diagonal sets use the properties that cells on the same diagonal share row - col or row + col.

Pruning: the key to performance

Without pruning, backtracking is just brute force. Good pruning strategies:

• Constraint propagation: eliminate choices that violate known constraints before recursing.
• Ordering heuristics: try the most constrained choices first (fail early).
• Bound estimation: if the remaining best-case outcome cannot beat the current best, skip the branch.

For N-Queens with N=12:

• Without pruning: explores ~479 million states
• With column + diagonal pruning: explores ~856,000 states
• A 500x improvement from simple constraint checks.

Backtracking vs. dynamic programming

Feature	Backtracking	Dynamic Programming
Goal	Find all solutions or any valid solution	Find the optimal solution
Approach	Explore and prune	Build from subproblems
Overlapping subproblems	Not required	Required
Memory	O(depth) for recursion	O(states) for table
Typical problems	Puzzles, permutations, constraint satisfaction	Optimization, counting

Some problems use both: backtracking with memoization is essentially top-down DP.

Common misconception

“Backtracking is just brute force.” Without pruning, yes. But effective backtracking with good pruning can solve problems billions of times faster than exhaustive search. The art is in designing pruning conditions that cut off as many bad branches as early as possible.

One thing to remember: The backtracking template — choose, explore, un-choose — is universal. Once you internalize it, every constraint satisfaction problem becomes a matter of defining what “valid” means and what “state” looks like.