Recursion and Backtracking for Coding Interviews (2026 Guide)

Recursion and backtracking are the techniques behind every "generate all" and "place under constraints" coding interview question. Recursion solves a problem by calling the same function on a smaller input until it hits a base case; backtracking uses recursion to build a solution one choice at a time and undoes each choice after exploring it. If you learn one backtracking template and four questions to configure it, you can solve subsets, permutations, combinations, N-Queens, Sudoku, and word search with the same code shape.

This guide gives you that template in Python, the recursion trees that explain its complexity, and the pruning moves that keep it fast.

Key Takeaways

• Every recursive function needs a base case that stops it and a recursive step that moves strictly toward that base case.
• Backtracking is a fixed loop: choose, recurse, un-choose. Problems differ only in the state, the choices, the stopping rule, and the pruning rule.
• Draw the recursion tree before coding. Its branching factor and depth give you the time complexity directly.
• Subsets use a start index, permutations use a used array, and combinations add a length cap. That is most of the difference.
• Pruning (sorting and breaking early, constraint sets, skipping duplicates) turns a timeout into a pass without changing the template.
• Small constraints, usually n of 20 or less, are the clearest signal that an exponential backtracking search is expected.

What Is Recursion, and What Makes a Good Base Case?

Recursion is a function that solves a problem by calling itself on a smaller instance of the same problem. It has two required parts: a base case that returns an answer directly, and a recursive case that reduces the input and combines the result.

def my_pow(x, n):
    if n < 0:
        return 1 / my_pow(x, -n)
    if n == 0:
        return 1.0
    half = my_pow(x, n // 2)
    return half * half if n % 2 == 0 else half * half * x

This is Pow(x, n) (LeetCode 50). The base case is n == 0. Each call halves n, so it runs in O(log n) time and O(log n) stack space.

A good base case has three properties:

1. It is reachable. Every recursive call must move toward it. If n can skip past zero, you recurse forever.
2. It covers the smallest inputs. Empty list, null node, zero, single character. Most bugs come from missing one of these.
3. It returns the right identity value. An empty sum is 0, an empty product is 1, an empty path still counts as one subset.

When you are unsure, trust the recursion. Assume the call on the smaller input returns the correct answer, then ask only: "Given that, how do I build the answer for this input?" This "leap of faith" is how most binary tree interview questions are solved, since a tree is a recursive structure by definition.

How Do Recursion Trees Reveal Time Complexity?

A recursion tree is a diagram where each node is one function call and its children are the calls it makes. Total work equals the number of nodes times the work done per node.

Here is naive Fibonacci, fib(n) = fib(n - 1) + fib(n - 2), for n = 5:

                    fib(5)
                 /          \
            fib(4)          fib(3)
           /      \         /     \
       fib(3)   fib(2)   fib(2)  fib(1)
       /    \    /   \    /   \
   fib(2) fib(1) ... ...  ...  ...

The tree branches twice per level and is about n levels deep, so the call count grows exponentially, roughly O(2^n). Notice fib(3) and fib(2) appear more than once. Repeated subtrees are the signal that memoization will help, which is where recursion turns into dynamic programming. Our dynamic programming patterns guide picks up from that point.

Use this table to estimate complexity from the tree shape:

Space complexity for recursion is at least the maximum depth of the tree, because each active call holds a stack frame. For a refresher on reading these bounds, see the Big O notation cheat sheet.

What Is the Universal Backtracking Template?

Backtracking is depth-first search over a tree of partial solutions: at each node you make a choice, recurse, and then undo that choice so the next branch starts from a clean state. Every backtracking problem fits this shape:

def solve(data):
    results = []
    path = []

    def backtrack(state):
        if is_complete(state):
            results.append(path[:])
            return
        for choice in choices(state):
            if not is_valid(choice, state):
                continue
            path.append(choice)
            backtrack(next_state(state, choice))
            path.pop()

    backtrack(initial_state)
    return results

Before you write a line, answer four questions out loud. Interviewers hear a structured plan, and you get a configuration for the template:

1. State: what do I need to know at this node? (An index, a used array, a remaining target, a board position.)
2. Choices: which options can I pick next?
3. Goal: when is the path complete and worth recording?
4. Prune: which choices are invalid or provably useless?

This table is the core of the guide. It shows how the same template becomes six different classic problems:

The path[:] copy matters. path is one shared list that gets mutated for the entire search, so appending it directly would leave you with many references to the same empty list.

Subsets, Permutations, and Combinations

These three problems are the foundation of backtracking interview questions. Learn how they differ and most variants become small edits.

Subsets: record at every node

def subsets(nums):
    result, path = [], []

    def backtrack(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

The start index guarantees each element is considered only after the ones before it, so [1, 2] and [2, 1] are never both produced. The recursion tree for [1, 2, 3]:

                 []
          /      |      \
       [1]      [2]     [3]
      /   \      |
  [1,2] [1,3]  [2,3]
    |
 [1,2,3]

There are 8 nodes, one per subset, which is 2^3. Copying each subset costs up to n, so the time is O(n × 2^n).

Permutations: a used array instead of a start index

def permute(nums):
    result, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

Order matters for permutations, so every unused element is a valid next choice. The first level has n branches, the next n - 1, and so on, giving n! leaves and O(n × n!) total time.

Combinations: subsets with a length cap

def combine(n, k):
    result, path = [], []

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

    backtrack(1)
    return result

The loop's upper bound is the first pruning trick in this guide. If you still need k - len(path) numbers, there is no point starting from a number so high that not enough remain. Without that bound the code is still correct, just slower.

Handling duplicates

When the input has duplicate values, sort first, then skip a value that equals its neighbor at the same tree level:

def subsets_with_dup(nums):
    nums.sort()
    result, path = [], []

    def backtrack(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

For Permutations II (47), the rule changes slightly: skip nums[i] when it equals nums[i - 1] and used[i - 1] is False. That forces equal values to be placed in their original order, so each distinct arrangement is built only once.

Constraint Problems: N-Queens and Sudoku

Constraint problems use the same template, but the pruning step does most of the work. The goal is to reject an invalid choice in O(1) before recursing on it.

N-Queens

N-Queens asks you to place n queens on an n by n board so that no two attack each other. Place one queen per row, so the state is the row number and the choices are the columns.

def solve_n_queens(n):
    result = []
    queens = []
    cols, diag, anti = set(), set(), set()

    def backtrack(row):
        if row == n:
            result.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for col in range(n):
            if col in cols or row - col in diag or row + col in anti:
                continue
            cols.add(col)
            diag.add(row - col)
            anti.add(row + col)
            queens.append(col)
            backtrack(row + 1)
            queens.pop()
            cols.remove(col)
            diag.remove(row - col)
            anti.remove(row + col)

    backtrack(0)
    return result

The key insight is that every cell on the same top-left to bottom-right diagonal shares the value row - col, and every cell on the same anti-diagonal shares row + col. Three sets turn the attack check into three constant-time lookups. The 8-queens puzzle has 92 solutions, and the 4-queens puzzle has 2, which makes a quick sanity test.

Partial recursion tree for n = 4, where X marks a pruned branch:

row 0:          c0                   c1
              /     \                 |
row 1:      c2       c3              c3
            |         |               |
row 2:      X        c1              c0
                      |               |
row 3:                X              c2  -> solution [1, 3, 0, 2]

The worst-case bound is about O(n!), since each row has at least one fewer safe column than the last, but pruning cuts the real search far below that.

Sudoku Solver

Sudoku Solver (37) is the same idea on a fixed 9 by 9 grid. The state is the next empty cell, the choices are digits 1 to 9, and the prune is "this digit already appears in the row, column, or 3 by 3 box."

def solve_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == ".":
                empty.append((r, c))
            else:
                rows[r].add(v)
                cols[c].add(v)
                boxes[(r // 3) * 3 + c // 3].add(v)

    def backtrack(k):
        if k == len(empty):
            return True
        r, c = empty[k]
        b = (r // 3) * 3 + c // 3
        for v in "123456789":
            if v in rows[r] or v in cols[c] or v in boxes[b]:
                continue
            board[r][c] = v
            rows[r].add(v); cols[c].add(v); boxes[b].add(v)
            if backtrack(k + 1):
                return True
            board[r][c] = "."
            rows[r].remove(v); cols[c].remove(v); boxes[b].remove(v)
        return False

    backtrack(0)

Two differences from the generation problems are worth naming in an interview. First, the function returns a boolean and stops at the first solution, since one is enough. Second, the box index formula (r // 3) * 3 + c // 3 maps each cell to one of nine boxes. Interviewers often ask how you would speed it up; the standard answer is to fill the empty cell with the fewest legal digits first.

Word Search: Backtracking on a Grid

Word Search (79) asks whether a word can be traced through adjacent cells of a grid without reusing a cell. It is backtracking where the "path" is a set of visited cells.

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False
        board[r][c] = "#"
        found = (backtrack(r + 1, c, i + 1) or backtrack(r - 1, c, i + 1)
                 or backtrack(r, c + 1, i + 1) or backtrack(r, c - 1, i + 1))
        board[r][c] = word[i]
        return found

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

Overwriting the cell with # marks it as visited without a separate set, and restoring it is the un-choose step. This is the difference from plain grid DFS covered in our graph algorithms guide: DFS for counting islands marks cells permanently, while backtracking unmarks them so other paths can use them.

Complexity is O(m × n × 3^L): each of the m × n starting cells launches a search, and after the first step each cell has at most three unvisited neighbors. For Word Search II (212), where you search for many words, combine this with a trie so you share prefixes across words.

Pruning Techniques That Turn Timeouts Into Passes

Pruning is any check that stops the search from entering a branch that cannot produce a valid answer. A correct backtracking solution without pruning often times out on larger tests. These six moves cover most interview cases:

Here is sort-and-break in Combination Sum:

def combination_sum(candidates, target):
    candidates.sort()
    result, path = [], []

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

    backtrack(0, target)
    return result

Passing i instead of i + 1 allows the same number to be reused, which is the only change from the combinations template. The break (not continue) is the prune: once one candidate is too large, every later candidate is too.

Common Recursion and Backtracking Mistakes

Most failed backtracking attempts in interviews come from a small set of bugs. Check for these before you say "done":

• Appending path instead of path[:]. Every stored result ends up as the same list.
• Forgetting to un-choose. If you add to used, a set, or the board, you must undo it after the recursive call, on every branch.
• Returning inside the loop too early. In generation problems, a return inside the loop skips the remaining choices.
• Wrong duplicate condition. It is i > start, not i > 0, for subsets and combinations.
• Deep recursion in Python. CPython's default recursion limit is 1,000 frames, per the Python sys module documentation. Backtracking depth is usually small, but recursive DFS on a long linked list or large grid can hit it.

If you freeze on the recursive step, say what you know: the state, the choices, the goal. Our guide on what to do when stuck in a coding interview covers how to recover without going silent, and how to think out loud shows how to narrate the four template questions so the interviewer can follow.

Practice List: Recursion and Backtracking Problems by Stage

Work through these in order. Each stage adds one new idea to the template. The numbers are LeetCode problem IDs.

Stages 2 through 4 are where most interview questions come from. Curated lists like NeetCode 150 include a backtracking section built from many of these same problems; see our comparison of Blind 75, NeetCode 150, and Grind 75 to decide which list to follow. For how backtracking fits next to sliding window, BFS, and the other core techniques, the coding interview patterns cheat sheet puts every pattern on one page.

A practical routine is to write the universal template from memory at the start of each session, then solve two problems from the current stage without looking at notes. Once stage 6 feels routine, mix backtracking problems in with other patterns so you practice recognizing them, not just executing them.