Backtracking cheatsheet

🧩 Backtracking

Build answers one choice at a time: choose, explore, un-choose, and prune branches that can't work.

Recognize the pattern

"Return all" subsets / combinations / permutations → backtracking over a decision tree
Tiny limits (n ≤ ~20 for 2ⁿ, n ≤ ~9 for n!) → an exponential search is expected
Pick numbers that sum to a target → combinations with a start index + sort and break when too big
Place items under rules (N-Queens, Sudoku) → try each option, check conflicts in O(1) with sets
Find a word or path in a grid → DFS, mark the cell visited, restore it on the way back
Input has duplicates but answers must be unique → sort, then skip equal siblings
Build strings from per-position options (phone keypad, letter case) → one tree level per position

The template

One shared path; record a copy; undo exactly what you did.

Python template

def solve(nums: list[int]) -> list[list[int]]:
    res: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        if is_complete(path):
            res.append(path[:])   # copy!
            return
        for i in range(start, len(nums)):
            if not is_valid(nums[i]):
                continue          # prune
            path.append(nums[i])  # choose
            backtrack(i + 1)      # explore
            path.pop()            # un-choose

    backtrack(0)
    return res

Subsets & combinations (start index)

Subsets record at every node; size-k combinations record at len(path) == k. Recurse with i + 1 (use once) or i (reuse allowed).

Python template

def subsets(nums: list[int]) -> list[list[int]]:
    res, path = [], []

    def bt(start: int) -> None:
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)
            path.pop()

    bt(0)
    return res

def combination_sum(cands: list[int],
                    target: int) -> list[list[int]]:
    cands = sorted(cands)
    res, path = [], []

    def bt(start: int, remain: int) -> None:
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(cands)):
            if cands[i] > remain:
                break          # sorted: rest too big
            path.append(cands[i])
            bt(i, remain - cands[i])  # reuse: i
            path.pop()

    bt(0, target)
    return res

Permutations (used array)

Order matters, so loop over every index and skip the used ones. Undo both path and used.

Python template

def permute(nums: list[int]) -> list[list[int]]:
    res, path = [], []
    used = [False] * len(nums)

    def bt() -> None:
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            bt()
            path.pop()
            used[i] = False

    bt()
    return res

Duplicates: sort + skip siblings

Start-index problems: skip when i > start. Permutations: skip when the equal previous value is not used (so equal values are always taken left to right).

Python template

nums.sort()
# start-index shapes (subsets II, combination sum II)
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i - 1]:
        continue

# permutations II
for i in range(len(nums)):
    if used[i]:
        continue
    if (i > 0 and nums[i] == nums[i - 1]
            and not used[i - 1]):
        continue

Grid DFS (mark, explore, restore)

Python template

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])

    def dfs(r: int, c: int, i: int) -> bool:
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols):
            return False
        if board[r][c] != word[i]:
            return False
        board[r][c] = "#"            # mark
        found = (dfs(r + 1, c, i + 1)
                 or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1)
                 or dfs(r, c - 1, i + 1))
        board[r][c] = word[i]        # restore
        return found

    return any(dfs(r, c, 0)
               for r in range(rows)
               for c in range(cols))

Constraint placement (N-Queens)

One queen per row; sets give O(1) conflict checks. Squares on the same \ diagonal share r - c, on the same / diagonal share r + c.

Python template

cols, diag, anti = set(), set(), set()

def place(r: int, n: int, queens: list[int]) -> None:
    if r == n:
        record(queens[:])
        return
    for c in range(n):
        if c in cols or r - c in diag or r + c in anti:
            continue
        cols.add(c); diag.add(r - c); anti.add(r + c)
        queens.append(c)
        place(r + 1, n, queens)
        queens.pop()
        cols.remove(c); diag.remove(r - c)
        anti.remove(r + c)

Operation costs

Operation	Time	Space
All subsets	O(n · 2ⁿ)	O(n) + output
Size-k combinations	O(k · C(n, k))	O(k) + output
All permutations	O(n · n!)	O(n) + output
Phone letter combos (n digits)	O(n · 4ⁿ)	O(n) + output
Word search (m×n grid, word length L)	O(m · n · 3ᴸ)	O(L)
N-Queens	O(n!)	O(n) + output

Watch for

res.append(path) stores a reference to one changing list: every result ends up identical (usually empty). Use path[:].
Undo everything you changed: path.pop(), used[i] = False, remove from sets, restore the grid cell.
Returning early from inside the loop before the undo line leaves stale state behind.
Duplicate skipping needs a sorted input and i > start (not i > 0), otherwise valid answers like [2, 2] vanish.
Reuse vs no reuse: recurse with i when an item can be picked again, i + 1 when it can't.
Grid DFS: check bounds before indexing board[r][c], and mark the cell before exploring neighbours.