Backtracking Comprehensive: From Template to Hard Problems

Backtracking is depth-first search over a decision tree with pruning. At each node you make a choice, explore its consequences recursively, and undo the choice before trying the next option. The pruning step is what makes backtracking practical: you abandon branches that cannot possibly lead to valid solutions.

Once you master the template, an entire family of problems collapses into the same pattern: subsets, permutations, combinations, N-Queens, Sudoku, word search, and more.

The universal template

Every backtracking algorithm follows this skeleton:

def backtrack(state, choices):
    if is_complete(state):
        record(state)
        return

    for choice in choices:
        if not is_valid(choice, state):
            continue                    # PRUNE

        apply(choice, state)            # CHOOSE
        backtrack(state, next_choices)   # EXPLORE
        undo(choice, state)             # UN-CHOOSE

The three steps are:

1. Choose: pick a candidate and apply it to the current partial state.
2. Explore: recurse with the updated state.
3. Un-choose: undo the change so the next iteration starts clean.

The pruning step (skipping invalid choices) is what distinguishes backtracking from brute force.

Backtracking vs brute force

	Brute Force	Backtracking
Approach	Generate all possibilities, filter	Build solutions incrementally, prune early
Pruning	None	Prune invalid branches
Space	Generate full candidates	Only partial candidates on stack
Performance	Always exponential	Often dramatically faster

Problem 1: N-Queens

Place N queens on an N x N chessboard so that no two queens attack each other (no shared row, column, or diagonal).

def solve_n_queens(n):
    """
    Find all valid N-Queens configurations.
    Time: O(N!) approximately (with pruning)
    Space: O(N) for the recursion stack and sets
    """
    results = []
    cols = set()
    pos_diag = set()   # row + col (positive diagonal)
    neg_diag = set()   # row - col (negative diagonal)

    board = [["." for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        if row == n:
            # All queens placed successfully
            results.append(["".join(r) for r in board])
            return

        for col in range(n):
            # Pruning: check if this position is under attack
            if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
                continue

            # Choose
            board[row][col] = "Q"
            cols.add(col)
            pos_diag.add(row + col)
            neg_diag.add(row - col)

            # Explore
            backtrack(row + 1)

            # Un-choose
            board[row][col] = "."
            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)

    backtrack(0)
    return results


# Print solutions for 4-Queens
solutions = solve_n_queens(4)
print(f"4-Queens has {len(solutions)} solutions:")
for i, sol in enumerate(solutions):
    print(f"\nSolution {i + 1}:")
    for row in sol:
        print(f"  {row}")
# 4-Queens has 2 solutions

N-Queens: just count solutions

def total_n_queens(n):
    """
    Count total N-Queens solutions (faster, no board construction).
    """
    count = 0
    cols = set()
    pos_diag = set()
    neg_diag = set()

    def backtrack(row):
        nonlocal count
        if row == n:
            count += 1
            return

        for col in range(n):
            if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
                continue

            cols.add(col)
            pos_diag.add(row + col)
            neg_diag.add(row - col)

            backtrack(row + 1)

            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)

    backtrack(0)
    return count


for n in range(1, 11):
    print(f"  {n}-Queens: {total_n_queens(n)} solutions")

Problem 2: Sudoku solver

Fill a 9x9 grid so each row, column, and 3x3 box contains digits 1-9 exactly once.

def solve_sudoku(board):
    """
    Solve a Sudoku puzzle in-place.
    Time: O(9^(empty cells)) worst case, much less with pruning
    Space: O(81) for the board
    """
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    # Initialize constraint sets from existing numbers
    empty_cells = []
    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                num = int(board[r][c])
                rows[r].add(num)
                cols[c].add(num)
                boxes[(r // 3) * 3 + c // 3].add(num)
            else:
                empty_cells.append((r, c))

    def backtrack(idx):
        if idx == len(empty_cells):
            return True  # All cells filled

        r, c = empty_cells[idx]
        box_idx = (r // 3) * 3 + c // 3

        for num in range(1, 10):
            # Pruning: check all three constraints
            if num in rows[r] or num in cols[c] or num in boxes[box_idx]:
                continue

            # Choose
            board[r][c] = str(num)
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_idx].add(num)

            # Explore
            if backtrack(idx + 1):
                return True

            # Un-choose
            board[r][c] = '.'
            rows[r].remove(num)
            cols[c].remove(num)
            boxes[box_idx].remove(num)

        return False  # No valid number for this cell

    backtrack(0)
    return board


# Example
board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]

solve_sudoku(board)
for row in board:
    print(" ".join(row))

Problem 3: word search

Given a 2D board and a word, find if the word exists by connecting adjacent cells (horizontally or vertically).

def word_search(board, word):
    """
    Search for word in 2D grid using backtracking.
    Time: O(M * N * 4^L) where L = len(word)
    Space: O(L) recursion stack
    """
    if not board or not word:
        return False

    rows, cols = len(board), len(board[0])

    def backtrack(r, c, idx):
        if idx == len(word):
            return True

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

        # Choose: mark as visited
        temp = board[r][c]
        board[r][c] = '#'

        # Explore all 4 directions
        found = (backtrack(r + 1, c, idx + 1) or
                 backtrack(r - 1, c, idx + 1) or
                 backtrack(r, c + 1, idx + 1) or
                 backtrack(r, c - 1, idx + 1))

        # Un-choose: restore
        board[r][c] = temp

        return found

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == word[0] and backtrack(r, c, 0):
                return True

    return False


board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
]
print(word_search(board, "ABCCED"))  # True
print(word_search(board, "SEE"))     # True
print(word_search(board, "ABCB"))    # False

Problem 4: generate parentheses

Generate all valid combinations of n pairs of parentheses.

def generate_parentheses(n):
    """
    Generate all valid parentheses combinations.
    Time: O(4^n / sqrt(n)) - nth Catalan number
    Space: O(n) recursion stack
    """
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return

        # Can add open paren if we haven't used all n
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)

        # Can add close paren if it won't make string invalid
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return result


for combo in generate_parentheses(3):
    print(f"  {combo}")
# ((()))
# (()())
# (())()
# ()(())
# ()()()

Pruning rules:

• Only add ( if open count < n.
• Only add ) if close count < open count (ensures validity).

These two rules guarantee every generated string is valid. No invalid strings are ever constructed.

Problem 5: palindrome partitioning

Partition a string so every substring is a palindrome.

def palindrome_partition(s):
    """
    Find all palindrome partitionings of string s.
    Time: O(n * 2^n)
    Space: O(n) recursion + O(n^2) cache
    """
    n = len(s)
    result = []

    # Precompute palindrome checks
    is_palindrome = [[False] * n for _ in range(n)]
    for i in range(n):
        is_palindrome[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                is_palindrome[i][j] = (length == 2 or is_palindrome[i + 1][j - 1])

    def backtrack(start, path):
        if start == n:
            result.append(path[:])
            return

        for end in range(start, n):
            if is_palindrome[start][end]:
                path.append(s[start:end + 1])
                backtrack(end + 1, path)
                path.pop()

    backtrack(0, [])
    return result


for partition in palindrome_partition("aab"):
    print(f"  {partition}")
# ['a', 'a', 'b']
# ['aa', 'b']

Problem 6: subset sum

Find all subsets that sum to a target value.

def subset_sum(nums, target):
    """
    Find all subsets that sum to target.
    Time: O(2^n) worst case
    Space: O(n) recursion stack
    """
    result = []
    nums.sort()  # Sort for pruning

    def backtrack(start, remaining, path):
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(nums)):
            # Skip duplicates
            if i > start and nums[i] == nums[i - 1]:
                continue

            # Pruning: if current number is too large, all future will be too
            if nums[i] > remaining:
                break

            path.append(nums[i])
            backtrack(i + 1, remaining - nums[i], path)
            path.pop()

    backtrack(0, target, [])
    return result


print(subset_sum([10, 1, 2, 7, 6, 1, 5], 8))
# [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Problem 7: combination sum (elements reusable)

def combination_sum(candidates, target):
    """
    Find combinations that sum to target. Each number can be used
    unlimited times.
    Time: O(N^(T/M)) where T=target, M=min(candidates)
    """
    result = []
    candidates.sort()

    def backtrack(start, remaining, path):
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # Pruning

            path.append(candidates[i])
            backtrack(i, remaining - candidates[i], path)  # i, not i+1 (reuse allowed)
            path.pop()

    backtrack(0, target, [])
    return result


print(combination_sum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]

Problem 8: letter combinations of a phone number

def letter_combinations(digits):
    """
    Generate all letter combinations for phone number digits.
    Time: O(4^n * n) where n = len(digits)
    """
    if not digits:
        return []

    phone = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }

    result = []

    def backtrack(idx, current):
        if idx == len(digits):
            result.append(current)
            return

        for letter in phone[digits[idx]]:
            backtrack(idx + 1, current + letter)

    backtrack(0, "")
    return result


print(letter_combinations("23"))
# ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Problem 9: permutations with duplicates

def permutations_unique(nums):
    """
    Generate all unique permutations.
    Time: O(n! / (k1! * k2! * ...))
    """
    result = []
    nums.sort()
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue

            # Skip duplicates: only use a duplicate if the
            # previous identical element was used
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result


print(permutations_unique([1, 1, 2]))
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Time complexity analysis

Backtracking time complexity depends heavily on pruning effectiveness.

Problem	Without Pruning	With Pruning	Actual
N-Queens	O(N^N)	O(N!)	Much less in practice
Sudoku	O(9^81)	O(9^(empty))	Fast with constraint propagation
Subsets	O(2^n)	O(2^n)	Cannot prune subsets
Permutations	O(n!)	O(n!)	Cannot prune permutations
Combination Sum	O(N^T)	O(N^(T/M))	Sorting enables early termination
Palindrome Part.	O(n * 2^n)	O(n * 2^n)	Precomputed palindrome check helps

General rule: The branching factor is the number of choices at each step, and the depth is the length of a complete solution. Total nodes in the decision tree = branching_factor^depth.

Optimization tips

1. Sort the input for early termination

# Without sorting: must check all candidates
for num in candidates:
    if num > remaining:
        continue  # Can't skip the rest

# With sorting: break early
candidates.sort()
for num in candidates:
    if num > remaining:
        break  # All remaining are too large

2. Use sets for O(1) constraint checking

# N-Queens: O(1) attack checks using sets
cols = set()
pos_diag = set()  # row + col
neg_diag = set()  # row - col

# O(1) to check if position is safe
if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
    continue

3. Precompute expensive checks

# Palindrome partitioning: precompute all palindrome substrings
# Instead of checking O(n) per substring during backtracking
is_palindrome = [[False] * n for _ in range(n)]
# Fill in O(n^2) total, then O(1) lookups

4. Use in-place modification instead of creating new objects

# SLOW: create new list each time
backtrack(path + [nums[i]])

# FAST: modify in place, undo after
path.append(nums[i])
backtrack(path)
path.pop()

Practice problems

Problem	Difficulty	Pattern
Subsets (LC 78)	Medium	Include/exclude each element
Permutations (LC 46)	Medium	Pick from remaining
Combination Sum (LC 39)	Medium	Reusable elements
N-Queens (LC 51)	Hard	Row-by-row placement
Sudoku Solver (LC 37)	Hard	Cell-by-cell filling
Word Search (LC 79)	Medium	Grid DFS
Generate Parentheses (LC 22)	Medium	Count-based pruning
Palindrome Partitioning (LC 131)	Medium	Substring partitioning
Subsets II (LC 90)	Medium	Skip duplicates
Permutations II (LC 47)	Medium	Skip duplicates
Combination Sum II (LC 40)	Medium	No reuse + skip duplicates
Letter Combinations (LC 17)	Medium	Fixed branching per digit
Restore IP Addresses (LC 93)	Medium	String partitioning

Key takeaways

1. Template is universal: Choose, explore, un-choose. Learn it once, apply it everywhere.
2. Pruning is the difference between backtracking and brute force. Good pruning can reduce runtime from hours to milliseconds.
3. Sort the input when possible for early termination.
4. Use sets for O(1) constraint checking instead of scanning.
5. Modify in place and undo, rather than copying data structures.
6. The decision tree’s branching factor and depth determine the worst-case time complexity.