Backtracking

Updated Nov 19, 2026 · 4 min read
On this page

    When a question asks for all subsets, permutations, combinations, board placements or word paths, there is usually no shortcut: you have to generate them. Backtracking does that with one recursive shape. Keep a partial answer, try each possible next choice, recurse, then undo the choice and try the next one. The undo step is what gives the pattern its name.

    The output itself is often exponential (there are 2ⁿ subsets and n! permutations), so the goal is not a better big-O. The goal is clean code that produces each answer once, and pruning that skips dead branches early.

    When to recognise it

    • "Return all …": all subsets, permutations, combinations, partitions, valid IP addresses, palindrome partitions.
    • Constraint puzzles: N-Queens, Sudoku, word search on a grid.
    • Small n: n ≤ 10 to 20 is a strong hint that exponential time is expected.
    • "Count the ways" with small input. If the input is larger and sub-problems repeat, the same recursion with a cache becomes DP 1D or DP 2D.

    The decision tree

    The decision tree for subsets of [1, 2, 3]: root [ ], children [1], [2], [3], then [1,2], [1,3], [2,3], then [1,2,3]. Every node is an answer. Children only use numbers after the last one picked, so [
    The decision tree for subsets of [1, 2, 3]: root [ ], children [1], [2], [3], then [1,2], [1,3], [2,3], then [1,2,3]. Every node is an answer. Children only use numbers after the last one picked, so [2, 1] never appears.

    Draw this tree first, even roughly. It answers the three questions that decide the code: what are the choices at a node, which nodes are answers (every node, or only leaves), and how do you avoid producing the same answer twice.

    Template

    def subsets(nums):
        """Choose / recurse / un-choose. Every node of the tree is an answer."""
        out, path = [], []
        def go(start):
            out.append(path[:])                 # copy: path keeps changing
            for i in range(start, len(nums)):
                path.append(nums[i])            # choose
                go(i + 1)                       # explore (start after i: no reuse, no reorder)
                path.pop()                      # un-choose
        go(0)
        return out

    The three lines in the loop are the pattern: choose (append), explore (go), un-choose (pop). Time O(n · 2ⁿ): 2ⁿ subsets, each copied in O(n).

    The variations change only a few lines:

    QuestionAnswer atNext choicesReuse allowed?
    Subsetsevery nodeindexes after ino: go(i + 1)
    Combinations of size kwhen len(path) == kindexes after ino: go(i + 1)
    Combination sumwhen remaining is 0indexes from iyes: go(i)
    Permutationsleaves (len == n)any unused indexno: used[]
    def permutations(nums):
        """Only leaves are answers; a used[] array replaces the start index."""
        out, path, used = [], [], [False] * len(nums)
        def go():
            if len(path) == len(nums):
                out.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True; path.append(nums[i])
                go()
                path.pop(); used[i] = False
        go()
        return out

    Pruning

    Pruning stops a branch as soon as it cannot lead to an answer. Sorting the candidates first often makes this a one-line break:

    def combination_sum(candidates, target):
        """Reuse allowed: recurse with i, not i + 1. Sorting lets us stop early (prune)."""
        candidates = sorted(candidates)
        out, path = [], []
        def go(start, remaining):
            if remaining == 0:
                out.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break                       # every later candidate is bigger too
                path.append(candidates[i])
                go(i, remaining - candidates[i])
                path.pop()
        go(0, target)
        return out

    Duplicates in the input. Sort, then skip a value equal to the one just before it at the same depth (i > start). This removes repeated answers without a set:

    def subsets_with_dup(nums):
        """Duplicates in the input: sort, then skip a value equal to its left neighbour at the same depth."""
        nums = sorted(nums)
        out, path = [], []
        def go(start):
            out.append(path[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i]); go(i + 1); path.pop()
        go(0)
        return out

    Grids: word search

    On a grid the choice is "which neighbour next". Mark the cell as used before recursing (for example, overwrite it with #) and restore it afterwards. That restore is the un-choose step. Time is about O(cells · 4ᴸ) for a word of length L, which is why pruning on the first wrong letter matters.

    Common bugs

    Two boxes: out.append(path), red, gives out = [[], [], [], ...]; out.append(path[:]), green, gives out = [[], [1], [1, 2], ...]. The path list is shared and empty at the end, so every saved answer mus
    Two boxes: out.append(path), red, gives out = [[], [], [], ...]; out.append(path[:]), green, gives out = [[], [1], [1, 2], ...]. The path list is shared and empty at the end, so every saved answer must be a copy.
    • Saving path instead of a copy. Every saved answer points to the same list.
    • Forgetting to undo, so choices leak into sibling branches.
    • go(i + 1) vs go(i) vs go(start + 1): the classic off-by-one. go(start + 1) is wrong in all three cases.
    • Duplicate answers from unsorted input or from skipping with i > 0 instead of i > start (which also skips valid answers like [2, 2]).
    • Not restoring a grid cell after exploring it.

    Say this in the interview

    • "I'll build the answer one choice at a time: choose, recurse, undo. There are 2ⁿ subsets, so O(n · 2ⁿ) is the best possible because that's the size of the output."
    • "I sort first so I can skip duplicate values at the same depth and stop early once a candidate is too large."

    Problems for this pattern

    1. Subsets: every node is an answer.
    2. Permutations: leaves only, with used[].
    3. Combination Sum: reuse allowed, prune with sorting.
    4. Letter Combinations of a Phone Number: one choice list per digit.
    5. Generate Parentheses: choose ( or ) while the counts allow it.
    6. Word Search: backtracking on a grid.
    7. Palindrome Partitioning: choose the next palindromic piece.
    8. N-Queens: prune with column and diagonal sets.
    9. Optimal Account Balancing: settle one debt at a time, skip equal balances.

    Related

    Tree DFS (backtracking is DFS on a tree you never build) · DP 1D (add a cache when sub-problems repeat) · Tries (Word Search II prunes with a trie)