Backtracking Explained

Backtracking is a technique for solving problems by exploring choices one at a time, and un-making a choice the instant it can’t lead anywhere useful. It’s recursion with a twist: try something, recurse deeper into the consequences of that choice, and once that branch is fully explored (successfully or not), undo the choice and try the next option. It shows up constantly in interviews and real code — generating all subsets or permutations of a set, solving Sudoku and N-Queens, finding every path through a maze, and searching any combinatorial space where a simple loop can’t enumerate the answers for you.

Overview: How Backtracking Works

Picture building a subset of the numbers {1, 2, 3} one element at a time. At each number you face a binary choice: include it, or skip it. Making these choices in sequence traces a path down a decision tree, and every complete path corresponds to one subset. Backtracking is the pattern for walking that entire tree with a depth-first search: make a choice, recurse into the resulting sub-problem, and once that branch has been fully explored, undo the choice (backtrack) before trying the next one at the same level. Because it is depth-first, backtracking never needs to hold more than one root-to-leaf path in memory at a time — that’s what keeps its space usage low even though the number of paths it visits can be huge.

Every backtracking function follows the same three-beat rhythm at each step: choose an option, explore by recursing with that option applied, then un-choose it by reversing exactly what you applied, so the next sibling branch starts from a clean, correct state. In pseudocode:

def backtrack(state):
    if is_solution(state):
        record(state)
        return
    for choice in get_choices(state):
        make_choice(state, choice)   # choose
        backtrack(state)             # explore
        undo_choice(state, choice)   # un-choose

The undo_choice step is what separates backtracking from plain recursion. Without it, the mutable state object would carry leftover changes from one branch into the next sibling branch, silently corrupting results. Many backtracking algorithms also add a pruning check — a condition that abandons a branch early once it’s clear it can never lead to a valid answer, which is what keeps otherwise-exponential search practical on many real inputs.

Time and Space Complexity

Backtracking explores a tree of choices, so its complexity is naturally described in terms of the branching factor (how many choices are available at each step) and the depth of the recursion (how many choices make up one full solution). In the worst case, without effective pruning, you visit every node of that tree, giving a time complexity of roughly O(b^d) where b is the branching factor and d is the depth — exponential, but this is unavoidable when the problem genuinely requires enumerating an exponential number of valid answers.

Problem Time Complexity Space (call stack + path) Why
All subsets of n items O(2^n) O(n) Each item is independently included or excluded, so there are 2 choices at each of n levels, giving 2^n leaves in the decision tree.
All permutations of n items O(n!) O(n) The first position has n choices, the second has n-1 remaining choices, and so on down to 1, giving n × (n-1) × … × 1.
Combination Sum (target T, m candidates) O(m^(T / min_candidate)), roughly O(T / min_candidate) Recursion depth is bounded by how many times the smallest candidate can be subtracted from the target; at each level you branch over up to m candidates.

Those space figures cover only the call stack and the shared path list — the extra working memory backtracking needs beyond the final answer — because recursion depth never exceeds roughly n (or the target, for combination sum) and each stack frame does O(1) work beyond referencing that shared path. The space needed to actually store the output is separate and often much bigger: storing all 2^n subsets costs O(2^n) space for the result list alone, and copying the current path into the results (path.copy(), an O(n) operation) at every one of the 2^n or n! leaves means the total work to build the full output is really O(n · 2^n) for subsets and O(n · n!) for permutations, not just O(2^n) or O(n!).

Examples

Example 1: All Subsets (the Power Set)

The include/skip decision described above translates directly into code. At every call, the current path is itself a valid subset (the empty path is a subset too), so it’s recorded immediately, and then the loop tries including each remaining item in turn.

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

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

    backtrack(0)
    return result


nums = [1, 2, 3]
print(subsets(nums))

Output:
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Tracing it: backtrack(0) first records the empty path [], then tries i=0 (value 1), pushing it and recursing with start=1 so 1 can never be picked again in that branch. That recursion records [1], then dives into 2 and 3, recording [1, 2] and [1, 2, 3] before running out of items and popping back up. Each pop() removes the most recently added element so the next sibling choice (skipping straight to 3 after backtracking past 2, for instance) starts from the correct partial path. The result is exactly the 23 = 8 subsets of a 3-element set.

Example 2: All Permutations

Permutations need every item exactly once, in every order, so instead of a start index the code tracks which items are already used with a boolean array, and a solution is complete once path is as long as nums.

def permutations(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    used: list[bool] = [False] * len(nums)
    path: list[int] = []

    def backtrack() -> None:
        if len(path) == len(nums):
            result.append(path.copy())
            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


nums = [1, 2, 3]
print(permutations(nums))

Output:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Unlike subsets, nothing is recorded until path reaches full length, because a partial permutation (say, just [1]) isn’t itself an answer. The used array is the state that gets chosen and un-chosen alongside path: marking used[i] = True before recursing and flipping it back to False after popping is what lets index i be reused in a different position of a later, sibling permutation.

Example 3: Combination Sum

Given a list of candidate numbers (each reusable any number of times) and a target, find every combination that sums exactly to the target. This adds a genuine pruning condition: stop exploring the instant the running total goes negative.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

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

    backtrack(0, target)
    return result


candidates = [2, 3, 6, 7]
target = 7
print(combination_sum(candidates, target))

Output:
[[2, 2, 3], [7]]

Notice the recursive call passes i, not i + 1, as the next start — that’s what allows a candidate like 2 to be reused (2 + 2 + 3 = 7). Following the branch that keeps picking candidate 2: after three 2’s the remaining target is 1, and every remaining candidate overshoots it, so remaining < 0 triggers and those branches return immediately without recording anything. Backtracking up, trying 2, 2, then 3 lands exactly on 0 and records [2, 2, 3]. Later, starting fresh from candidate 7 alone also hits 0 and records [7]. No other combination of these candidates reaches exactly 7.

How It Works Step by Step

To see the choose/explore/un-choose rhythm in slow motion, trace permutations on the tiny input nums = [1, 2], where used = [False, False] and path = [] at the start.

Step Action path used
1 Enter backtrack(); len(path)=0, not done. Try i=0 (value 1). [] [F, F]
2 Choose: used[0]=True, push 1. [1] [T, F]
3 Recurse; len(path)=1, not done. Try i=1 (value 2). Choose: used[1]=True, push 2. [1, 2] [T, T]
4 Recurse; len(path)=2 equals len(nums) — record a copy: [1, 2]. [1, 2] [T, T]
5 Un-choose: pop 2, used[1]=False. Inner loop ends, return up. [1] [T, F]
6 Un-choose: pop 1, used[0]=False. Move to i=1 (value 2) at the top level. [] [F, F]
7 Choose: used[1]=True, push 2. Recurse; try i=0 (value 1). Choose: used[0]=True, push 1. [2, 1] [T, T]
8 len(path)=2 — record a copy: [2, 1]. Un-choose both, loops end. [] [F, F]

The final result is [[1, 2], [2, 1]] — every possible ordering of the two items. Each row shows the state changing by exactly one push or pop, which is the discipline that makes backtracking correct: the state right before trying choice i is always identical to the state right after undoing choice i.

Common Mistakes

Mistake 1: Forgetting to copy the accumulator before saving it

It’s tempting to append path itself to result instead of a copy. Because path is the same list object being mutated throughout the whole recursion, every entry in result ends up pointing at that one object — and by the time the algorithm finishes, it has been popped all the way back to empty.

def subsets_wrong(nums: list[int]) -> list[list[int]]:
    result = []
    path = []

    def backtrack(start: int) -> None:
        result.append(path)  # BUG: stores a reference, not a copy
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result


nums = [1, 2, 3]
print(subsets_wrong(nums))

Output:
[[], [], [], [], [], [], [], []]

Eight subsets were correctly counted, but every one of them displays as [] because they all alias the same, now-empty path. The fix is the one used earlier: append path.copy() (equivalently list(path) or path[:]), which snapshots the current contents into a brand-new list that later mutations of path can’t touch.

Mistake 2: Using a mutable default argument as the accumulator

Default argument values in Python are created once, when the function is defined — not fresh on every call. Using a mutable default like a list as an accumulator means every call that doesn’t explicitly pass one shares the exact same list.

def make_path(item: int, path: list[int] = []) -> list[int]:
    path.append(item)
    return path


print(make_path(1))
print(make_path(2))

Output:
[1]
[1, 2]

The second call should intuitively produce [2], but it produces [1, 2] because it’s still appending to the very same default list created back when make_path was defined. This bug is especially dangerous in backtracking helpers, where an accumulator parameter is exactly the pattern that invites it. The fix is to default to None and create a fresh list inside the function body when needed:

def make_path(item: int, path: list[int] | None = None) -> list[int]:
    if path is None:
        path = []
    path.append(item)
    return path


print(make_path(1))
print(make_path(2))

Output:
[1]
[2]

Now each call without an explicit path starts from its own empty list, as intended.

Best Practices

  • Undo state exactly the way you applied it (matching push with pop, matching used[i] = True with used[i] = False), and do this unconditionally so a branch that finds nothing doesn’t leak state into its siblings.
  • Always store a copy of a mutable accumulator (path.copy(), list(path)) when saving it into a results list — never the live object.
  • Never use a mutable default argument (a list, dict, or set) as an accumulator parameter; default to None and initialize inside the function.
  • Prune as early as possible: check constraints while building a partial solution (as combination_sum does with remaining < 0) rather than only validating complete solutions, so invalid branches are abandoned before wasting time exploring them further.
  • Reach for backtracking when the problem asks you to enumerate all valid combinations, arrangements, or configurations under constraints — not when a single best answer via greedy choice or dynamic programming would do, since those are typically far cheaper.
  • Watch Python’s recursion limit (around 1000 by default) on backtracking over large or deep inputs; an iterative, explicit-stack rewrite avoids RecursionError when recursion depth could plausibly exceed it.
  • Use a boolean array or set for membership checks (like used) instead of scanning a list with in, so an accidental O(n) check doesn’t turn an already-exponential search into something even slower.

Practice Exercises

1. Generate Parentheses. Write a function that, given an integer n, returns every well-formed combination of n pairs of parentheses. Hint: track how many '(' and ')' you’ve placed so far; you may add '(' whenever you’ve used fewer than n of them, and you may add ')' only when doing so wouldn’t exceed the number of '(' already placed. For n = 3 you should get 5 combinations.

2. N-Queens Count. Implement a backtracking solution that places n queens on an n × n chessboard so that no two attack each other (same row, column, or diagonal), and return how many distinct solutions exist. Hint: place one queen per row, and before placing a queen in a column, check it against every queen placed in previous rows. For n = 4, the expected count is 2.

3. Subsets With Duplicates. Given a list that may contain duplicate values, such as [1, 2, 2], write a backtracking function that returns all unique subsets without any duplicate subset appearing twice in the output. Hint: sort the input first, then within a single level of the recursion’s loop, skip a candidate if it’s equal to the previous candidate you already tried at that same level.

Summary

  • Backtracking is depth-first search over a tree of choices, combined with an explicit undo step, used to enumerate all valid combinations or arrangements that satisfy some constraint.
  • The core pattern at every step is choose → explore (recurse) → un-choose, and the un-choose step must exactly reverse the choose step.
  • Complexity is generally exponential or factorial (O(2^n) for subsets, O(n!) for permutations, O(b^d) in general) because the algorithm is visiting a branching tree of choices, not because it’s inefficient — exhaustive enumeration inherently costs this much.
  • Always copy a mutable accumulator before saving it to a results list, and never default a mutable object as an accumulator parameter — both are classic, easy-to-miss bugs.
  • Prune early when possible, watch recursion depth on large inputs, and reach for backtracking specifically when you need all valid answers, not just one.