Backtracking

Back to Index

Use when: generating all valid combinations, permutations, or subsets; constraint satisfaction.

Signal words: all combinations, all permutations, all subsets, generate, find all valid, N-Queens, Sudoku.

Core Idea

DFS + undo. At each step, make a choice, recurse, then undo the choice to explore other branches.

Template

def backtrack(start, current):
    if is_complete(current):
        result.append(current[:])  # snapshot, not reference
        return
 
    for choice in get_choices(start):
        if is_valid(choice, current):
            current.append(choice)
            backtrack(next_start(choice), current)
            current.pop()  # undo
 
result = []
backtrack(0, [])

Pruning

The difference between slow and fast backtracking is pruning - skipping branches early when you know they can’t lead to a valid answer.

Common Patterns

• Subsets: choose to include or exclude each element
• Permutations: pick from remaining elements (no index tracking needed if using used[] set)
• Combinations: pick from index forward to avoid duplicates

Deduplication with duplicates in input

Sort first, then skip choices[i] == choices[i-1] when i > start.

---

Problems Using This Pattern