Top 10 Backtracking Patterns for Coding Interviews (2026)

The short answer

Backtracking is DFS with undo. Ten recurring templates: subsets, permutations, combinations, combination sum, palindrome partitioning, word search on grid, N-Queens, Sudoku solver, phone letter combinations, and restore IP addresses. The common shape is: pick a choice, recurse, unpick. Master the subsets template first; the rest are variations.

Backtracking problems look intimidating and expand to many solutions. The implementation is a short recursive function that picks a choice, recurses, then undoes the choice. Every backtracking problem in interviews is a variation of one of ten templates.

This guide walks each template with a clean Python implementation. Memorize the first three and the rest become obvious.

Pattern 1: Subsets

Given [1,2,3], return all subsets. For each element, choose to include or exclude.

def subsets(nums):
    out, path = [], []
    def backtrack(i):
        if i == len(nums):
            out.append(path[:])
            return
        backtrack(i + 1)          # exclude
        path.append(nums[i])
        backtrack(i + 1)          # include
        path.pop()                # undo
    backtrack(0)
    return out

The canonical backtracking shape. LeetCode 78.

Pattern 2: Permutations

All orderings. Track which elements are used; try each unused one at each position.

def permutations(nums):
    out, path, used = [], [], [False] * len(nums)
    def backtrack():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i, n in enumerate(nums):
            if used[i]: continue
            used[i] = True
            path.append(n)
            backtrack()
            path.pop()
            used[i] = False
    backtrack()
    return out

Pattern 3: Combinations

Choose k items from n. Pick an element, recurse starting from the next index, unpick.

def combine(n, k):
    out, path = [], []
    def backtrack(start):
        if len(path) == k:
            out.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1)
            path.pop()
    backtrack(1)
    return out

Pattern 4: Combination Sum

Find all combinations that sum to a target. Elements can be reused; recurse from i, not i+1.

def combination_sum(candidates, target):
    out, path = [], []
    def backtrack(start, remaining):
        if remaining == 0:
            out.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: continue
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()
    backtrack(0, target)
    return out

Pattern 5: Palindrome Partitioning

Split a string into substrings where each piece is a palindrome. Backtrack on cut positions.

def partition(s):
    out, path = [], []
    def is_pal(a, b):
        while a < b:
            if s[a] != s[b]: return False
            a, b = a + 1, b - 1
        return True
    def backtrack(start):
        if start == len(s):
            out.append(path[:])
            return
        for end in range(start, len(s)):
            if is_pal(start, end):
                path.append(s[start:end + 1])
                backtrack(end + 1)
                path.pop()
    backtrack(0)
    return out

Pattern 6: Word Search on Grid

Does a word exist in a 2D grid of letters? DFS from every starting cell, mark visited, unmark on return.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word): return True
        if r < 0 or r >= rows or c < 0 or c >= cols: return False
        if board[r][c] != word[i]: return False
        tmp, board[r][c] = board[r][c], '#'
        found = any(dfs(r + dr, c + dc, i + 1)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = tmp
        return found
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Pattern 7: N-Queens

Place N queens on an NxN board so no two attack. Try each column in each row; use sets to track attacked columns, diagonals, and anti-diagonals.

def solve_n_queens(n):
    out, cols, diag, anti = [], set(), set(), set()
    board = [['.'] * n for _ in range(n)]
    def backtrack(r):
        if r == n:
            out.append([''.join(row) for row in board])
            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)
            board[r][c] = 'Q'
            backtrack(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)
            board[r][c] = '.'
    backtrack(0)
    return out

Pattern 8: Sudoku Solver

Find an empty cell, try each digit 1 to 9, check row, column, and 3x3 box, recurse on next empty cell. Return True when no empties remain.

Pattern 9: Phone Letter Combinations

Given "23", return all letter combinations from a phone keypad. For each digit, recurse with every letter it maps to appended to the path.

def letter_combinations(digits):
    if not digits: return []
    mapping = {'2':'abc','3':'def','4':'ghi','5':'jkl',
               '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    out, path = [], []
    def backtrack(i):
        if i == len(digits):
            out.append(''.join(path))
            return
        for ch in mapping[digits[i]]:
            path.append(ch)
            backtrack(i + 1)
            path.pop()
    backtrack(0)
    return out

Pattern 10: Restore IP Addresses

Given "25525511135", return all valid IPv4 addresses. Backtrack on cut positions, limit each segment to 3 characters, validate each piece (0 to 255, no leading zeros except single zero).

Common pitfalls to avoid

  • Appending the shared path directly to the result list. Always copy with path[:] or list(path); otherwise all your results point to the same list object.
  • Forgetting the undo step. Every mutation to state before a recursive call needs a matching undo after.
  • Choosing the wrong starting index for recursion. Combinations recurse with start = i + 1 (no reuse); combination sum recurses with start = i (reuse allowed). Mixing them produces duplicates or missing solutions.
  • Not pruning early. Checking a constraint before recursing often saves exponential work; checking after wastes the whole branch.
  • Deep copying when a swap-based approach would work. Permutations can swap in place and undo the swap, avoiding list copies entirely.

Practice sequence that works

Do subsets, permutations, and combinations first until each one takes five minutes. Then combination sum, phone letters, and palindrome partitioning. N-Queens and Sudoku last; they combine the templates with constraint tracking. Three weeks of 30 minutes a day covers all ten with confidence.

Frequently asked questions

What is the difference between backtracking and brute force?

Brute force tries every combination. Backtracking prunes the search tree by abandoning branches that cannot lead to a valid answer. Combination Sum is backtracking because we skip candidates larger than the remaining target. The savings compound exponentially on hard inputs.

Why pass path[:] instead of path?

path is a shared list across recursive calls. When you append the current path to the result, you want a snapshot of the current state. path[:] copies the list. Without the copy, the result ends up filled with references to the same list, which changes as recursion continues.

What is the time complexity of backtracking?

Depends on the problem but typically exponential. Subsets is O(2^n * n), permutations is O(n! * n), N-Queens is roughly O(n!) with pruning. The work at each leaf is the dominant factor; the recursion depth is bounded by the problem size.

How do I handle duplicates in input?

Sort the input first. In the loop, skip an element if it equals the previous one and the previous one was not just chosen. This keeps you from generating the same path through two different orderings.

When should I iterate instead of recurse?

For subsets specifically, iterating from the empty set and doubling on each new element is cleaner. For permutations, Python's itertools.permutations is already optimized. Interview judges usually want to see the recursive template because it generalizes to problems without built-in helpers.

Can I memoize a backtracking function?

Sometimes. Backtracking that produces a count or boolean can be turned into dynamic programming if subproblems repeat. Backtracking that produces all solutions cannot be memoized because each path is unique. Use memoization when the output is a single number, not a collection.

Interview day strategy

On any new backtracking problem, start by naming the template out loud: "This is subsets with constraint X" or "This is combination sum with modification Y." If you cannot name it in 60 seconds, the problem likely needs a different technique. Clarify input constraints before coding: can elements repeat, are there duplicates, is the output order sensitive. Write the recursive signature first, then the base case, then the recursive step. The undo step comes last and is easy to forget under pressure.

Leave a Comment