Backtracking

In coding interviews, many problems feel challenging not because the underlying logic is complicated, but because the search space is enormous. A brute-force “try every possibility” approach often leads to exponential runtime, complex branching, and errors introduced by managing mutable state across attempts.

Backtracking is the standard interview pattern for these problems. It gives you a disciplined way to explore a decision tree: build a candidate step by step, reject it as soon as it becomes invalid, and revert your last decision to try the next option. The big win is not that backtracking magically removes exponential complexity; the win is that it lets you avoid wasted work by cutting off dead branches early and keeps your code readable.

In this article, we’ll learn what backtracking is, how to apply it using a Python code implementation, and understand its complexity.

What is Backtracking?

Backtracking is a depth-first search (DFS) over a space of choices. You maintain a partial solution (often called a path) and try to extend it step by step. At each step, you:

1. Choose an option
2. Explore deeper (recursive DFS)
3. Undo the choice (revert state)
4. Repeat with the next option

A clean way to summarize it is:

This pattern shows up whenever the output is not a single number but a set of valid constructions. These constructions can be a list (subset/permutation), a string (parentheses), or a grid assignment (Sudoku).

Understanding Backtracking using a real-life example

Imagine you’re trying to guess a PIN, but you get feedback after each digit. You pick the first digit, and the system immediately tells you whether any valid PIN can start with that prefix. If you try 7 and it says, “No valid code starts with 7,” you stop right there and try a different first digit. You don’t keep guessing the remaining digits because once the prefix is invalid, every longer guess built on it is guaranteed to fail.

That’s the essence of pruning. Backtracking is built on the idea that partial progress is informative: a partially built solution can already tell you whether you’re on a viable path. If the current partial solution is impossible, you cut off that branch early instead of wasting time exploring it further.

When should you use Backtracking?

Backtracking should come to mind when the problem asks you to build or enumerate solutions, especially under constraints. The table below helps you out in this regard:

The key idea behind backtracking is simple:

Backtracking structure

Backtracking feels “hard” only when the recursion is treated as magic and it becomes predictable once you define the search in plain terms before you write any code. The fastest way to do that is to answer five questions up front, these determine your recursion, your loop, and your undo logic.

• What am I building? The partial solution you’re extending (a path list, a string under construction, or a grid/board assignment).
• What can I try next? The candidate choices available from the current state (next number, next character, next cell, next direction).
• What makes a choice illegal? The constraints that must always remain true (already used, violates sum/length, conflicts on row/col/diagonal, revisits a cell).
• When do I record an answer? The goal condition that defines a complete solution. Some problems record only at the leaf (permutations), while others record at every node (subsets).
• What must I revert before trying the next choice? Every state change you made while exploring a branch, i.e., path.pop(), unmark used/visited, restore a board cell, remove from a set/map, roll back a running sum.

Once these are explicit, most backtracking problems reduce to the same shape: loop over choices $\rightarrow$→ validate $\rightarrow$→ choose $\rightarrow$→ recurse $\rightarrow$→ then undo. The differences across problems are mostly just what the state is and how you prune.

Pruning while backtracking

Backtracking becomes interview-grade when you prune early. Pruning means detecting impossibility at a partial state, not at the end.

Examples of pruning checks:

• Generate Parentheses: Never allow close > open, and never allow open > n
• N-Queens: Never place a queen if it conflicts in column/diagonal
• Combination Sum: stop if current sum exceeds target
• Word Search: Stop if the next character doesn’t match or cell is already visited

The earlier you can prove “this branch can’t succeed,” the more of the tree you avoid exploring.

Backtracking template in Python

Many candidates remember the shape of backtracking code but struggle on two critical details:

1. Where to record answers
2. How to undo

A stable template keeps those steps consistent, so your code stays correct under pressure.

result = []
path = []

def backtrack(state):
    # 1) Goal: record when complete
    if goal_reached(state):
        # copy snapshot
        result.append(path[:])
        return

    # 2) Explore: try all choices
    for choice in choices(state):
        if not valid(choice, state):
            continue

        # 3) Choose
        apply(choice, state)
        path.append(choice)

        # 4) Recurse
        backtrack(state)

        # 5) Undo
        path.pop()
        undo(choice, state)

backtrack(initial_state)
return result

Two details matter more than they look:

1. You typically append a copy of path, not the same list reference.
2. The undo step must perfectly restore the state for the next iteration.

Example 1: Subsets (the “record at every node” version)

Subsets are an ideal first backtracking problem because every partial subset is always valid there’s nothing to prune. This makes it perfect for learning the core mechanics, i.e., exploring choices with recursion, using a start index to avoid duplicates, and undoing changes cleanly between branches.

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

    def backtrack(start):
        # Every partial path is a valid subset
        result.append(path[:])

        for i in range(start, len(nums)):
            path.append(nums[i])       # choose
            backtrack(i + 1)           # explore
            path.pop()                 # undo

    backtrack(0)
    return result


def print_subsets(nums, subsets_list):
    print(f"Input: {nums}")
    print(f"Total subsets: {len(subsets_list)}")
    print("-" * 75)

    for idx, s in enumerate(subsets_list, start=1):
        print(f"{idx:>2}. {s}")

if __name__ == "__main__":
    nums = [1, 2, 3]
    ans = subsets(nums)
    print_subsets(nums, ans)

Explanation of the algorithm

What’s happening structurally is important. Each recursion call represents “I am deciding the next element starting from index start.” The loop at line 9 tries all possible next picks, and start ensures you never go backward, so you never produce the same subset in multiple orders.

The following illustration for a recursion tree shows exactly how the code builds subsets, i.e., each node is the current path, and every edge is a “choose next element, recurse, then pop to backtrack” step.

Example 2: Permutations (introducing used as a constraint)

Permutations feel similar to subsets because you still build a path step-by-step, but the constraint is completely different. In subsets, you move forward with a start index to avoid reusing earlier positions. In permutations, there is no “start” because at each step you’re allowed to pick any remaining number. The only rule is that each element can appear once in the current arrangement.

That’s why we keep a used array. It marks which elements have already been used in the current permutation (path). Each recursive call tries all unused elements, and after exploring one choice, we undo it so the next choice starts from a clean state.

def permute(nums):
    result = []                 # Stores all completed permutations
    path = []                   # Current permutation being built
    used = [False] * len(nums)  # used[i] = True means nums[i] is already in 'path'

    def backtrack():
        # Goal: if path has length n, we formed one full permutation
        if len(path) == len(nums):
            result.append(path[:])      # Append a COPY of path (snapshot)
            return

        # Try placing each unused number in the next position
        for i in range(len(nums)):
            if used[i]:
                continue                # Skip numbers already used in this permutation

            # Choose
            used[i] = True              # Mark nums[i] as used
            path.append(nums[i])        # Add it to the current permutation

            # Explore
            backtrack()                 # Recurse to fill the next position

            # Undo (backtrack)
            path.pop()                  # Remove last chosen number
            used[i] = False             # Unmark it so other branches can use it

    backtrack()
    return result


def print_permutations(nums, perms):
    print(f"Input: {nums}")
    print(f"Total permutations: {len(perms)}")
    print("-" * 52)

    for idx, p in enumerate(perms, start=1):
        print(f"{idx:>2}. {p}")


if __name__ == "__main__":
    nums = [1, 2, 3]
    perms = permute(nums)
    print_permutations(nums, perms)

Complexity analysis

Backtracking often looks “expensive” because it explores many possibilities, and in many of these problems the number of valid solutions is already huge. If a problem can output (2^n) subsets or (n!) permutations, no algorithm can be faster than the time needed to generate that many results. In other words, exponential runtime here isn’t a mistake it’s often the minimum cost of enumeration.

Typical growth patterns you’ll see:

• Subsets: (2^n)
• Permutations: (n!)
• Combinations (choose (k) from (n)): $\binom{n}{k}$(kn​)

Space usage is usually manageable because you only store the current recursion path:

• Recursion stack: O(depth) often O(n) or O(k)
• Helper state: typically O(n) e.g., used, visited, sets)

What interviewers want is not “make it polynomial,” but: explain why the search space is inherently large, then show that your pruning cuts off doomed branches early, so you’re not doing obviously wasted work.

Backtracking vs. related patterns

Backtracking also benefits from a quick “don’t misuse it” comparison. The table below compares backtracking with some other commonly used coding patterns:

Common mistakes when using Backtracking

Backtracking is conceptually simple, but state mistakes are common:

• Forgetting to undo (pop(), unmark used, restore board cell)
• Appending path without copying (result.append(path) creates aliasing bugs)
• Recording answers at the wrong time (too early or only at the leaf when partials should count)
• Not pruning early (checking constraints only at the end)
• Duplicate results when input contains duplicates (needs sorting + “skip duplicates at same depth” rule)