Skip to content
Tutorials Center
My learning

Topics

Lesson 63 of 225 ยท Recursion and Backtracking

Backtracking

Learn backtracking in Python: the choose-explore-undo template, the search tree, pruning, and worked examples such as binary strings and generating parentheses.

Imagine you are in a maze with many forks. You pick a path and keep walking. When you hit a dead end, you walk back to the last fork and try a different path. You never need to start over from the entrance. That is backtracking: a systematic way to explore all the possibilities of a problem by building a solution one decision at a time, and undoing the last decision whenever it leads nowhere.

Backtracking is recursion with an extra rule: after exploring a choice, you reverse it so that the next choice starts from a clean state. It solves puzzles and "generate all" problems: parentheses, subsets, permutations, N-Queens, Sudoku, word search, and many more. In this lesson you will learn the template, see the search tree it walks, and learn the single most important optimisation, pruning.

The search tree

Every backtracking problem can be drawn as a tree. Each node is a partial solution; each edge is a choice; each leaf is either a complete solution or a dead end. Take the problem "list all binary strings of length 3":

TEXT
                      ""
              /                \
            "0"                "1"
          /     \            /     \
       "00"     "01"      "10"     "11"
       /  \     /  \      /  \     /  \
    000  001  010  011  100  101  110  111

Backtracking performs a depth-first traversal of this tree: go down a choice, explore everything below, come back up, try the next choice. The whole path from the root to the current node is your partial solution, which you keep in a list and modify as you go.

The template: choose, explore, undo

TEXT
def backtrack(state):
    if state is a complete solution:      # 1. goal test
        record it
        return
    for choice in available choices:
        if choice is valid:               # 2. (pruning) skip hopeless choices
            make the choice               # 3. CHOOSE
            backtrack(new state)          # 4. EXPLORE
            undo the choice               # 5. UNDO (backtrack)

The "undo" step is what separates backtracking from plain recursion: because the same list is shared by every call, each call must leave it exactly as it found it.

Python All binary strings of length n

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are 2 choices at each of n levels, so 2^n leaves: 8 strings for n = 3 and 32 for n = 5. The time is O(n * 2^n) (each result costs O(n) to build), and the extra space is O(n) for the path and the recursion stack, not counting the output.

Why undo matters

What happens if you forget the undo? Every call keeps adding to the same list. Compare the correct version above with this broken one:

Python Forgetting to undo (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output is just ['00']: after the first leaf the path stays full, so every later call sees len(path) == 2, never loops, and the other three strings are never produced. Another classic bug is results.append(path) instead of results.append(list(path)): you store the same list object many times, and at the end they all show the final (empty) state. Always store a copy.

When a backtracking function returns the same wrong value many times, or only one result, suspect (1) a missing undo and (2) appending the shared path without copying it.

Pruning: do not walk into dead ends

Plain "generate everything and filter" wastes time exploring partial solutions that can never become valid. Pruning means checking a partial solution early and abandoning it as soon as no completion can work. Pruning does not change the answer; it changes how much of the tree you visit.

Let us find all binary strings of length n with no two adjacent 1s. First the brute force: generate all 2^n strings and test each.

Python Brute force versus pruning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions find the same 21 strings, but the brute force visits 127 nodes and the pruned one only 53. For bigger inputs the gap grows dramatically, which is why pruning is the main skill in backtracking. Good pruning rules ask: "given what I have chosen so far, is it still possible to finish?"

Worked example: generate parentheses

Problem. Given n, list all strings of n pairs of parentheses that are well formed: every ( is closed, and a ) never comes before its (. For n = 3: ((())), (()()), (())(), ()(()), ()()().

Brute force. Generate all 2^(2n) strings of ( and ) and keep the balanced ones. For n = 3 that is 64 strings to test; for n = 10 it is over a million, though only 16,796 are valid.

Backtracking with pruning. Build the string left to right and track two counters. You may add ( while fewer than n have been used. You may add ) only while there are more opens than closes. These two rules make an invalid prefix impossible, so every leaf is a valid answer and no filtering is needed.

TEXT
n = 2 (partial string, opens used, closes used)
                       ""
                       |
                      "("
                    /     \
               "(("         "()"
                |             |
              "(()"         "()("
                |             |
             "(())"        "()()"      <- 2 answers, no dead ends
Python Generate parentheses

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The counts 1, 2, 5, 14, 42, 132, 429 are the Catalan numbers. The number of results grows roughly like 4^n / (n^1.5), so any algorithm that lists them has exponential time; the backtracking one is optimal in the sense that its work is proportional to the output size (times n for building each string).

Worked example: combination sum

Problem. Given distinct positive numbers and a target, list all combinations (numbers may be reused) that add up to the target.

Here pruning is natural: once the running sum exceeds the target, stop. If the candidates are sorted, we can stop the whole loop at the first number that is too big, because the following ones are bigger still.

Python Combination sum with pruning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The start index prevents duplicates like [2, 3] and [3, 2]: we only ever pick candidates at positions >= start, so each combination is generated in one order only. Sorting plus break is a very common pruning pattern.

Complexity of backtracking

There is no single formula, because it depends on the size of the tree and how much pruning removes:

Problem Tree size (worst) Time
Binary strings of length n 2^n leaves O(n * 2^n)
Subsets of n items 2^n O(n * 2^n)
Permutations of n items n! O(n * n!)
Generate parentheses Catalan(n) results O(4^n / sqrt(n))
N-Queens n! upper bound, far fewer after pruning exponential

The space is usually O(depth of the tree) for the recursion and path, plus the output. Backtracking is exponential in the worst case, so it is only for problems where the input is small (n up to about 10 to 20) or where pruning is very effective. If the problem has overlapping sub-problems and you only need a count or an optimum, dynamic programming is usually much faster.

A checklist for designing a backtracking solution

  1. State: what does the partial solution look like (a list, a string, a board)?
  2. Choices: what can be chosen at each step?
  3. Constraints: which choices are invalid right now? (This is your pruning.)
  4. Goal: when is the partial solution complete?
  5. Undo: how do you reverse a choice exactly?
  6. Duplicates: could the same solution be reached by several orders? Use a start index, sorting, or a used set.

Common mistakes

  • Forgetting to undo, or undoing the wrong thing.
  • Storing the shared path without copying it.
  • Pruning too late (checking only at the leaf), which makes the search needlessly slow.
  • Pruning incorrectly and losing valid answers: test against a brute-force version on small inputs, as done above.
  • Generating duplicates from different orders of the same choices.
  • Using backtracking for optimisation problems with overlapping sub-problems, where DP is the right tool.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the three core steps inside the loop of a backtracking function?

    You make a choice, recurse to explore the consequences, then undo the choice so the next option starts from the same state.
  2. 2. What does pruning do?

    Pruning abandons a partial solution as soon as it cannot be completed, so fewer nodes are visited. The final answers stay the same.
  3. 3. A backtracking function appends the shared list path to results, and at the end every entry in results is empty. What is the likely bug?

    results holds many references to the same list. After backtracking undoes every choice, that list is empty. Store list(path) instead.
  4. 4. In generate parentheses, when may you add a closing parenthesis?

    A closing parenthesis needs an unmatched opening one before it, which is exactly when the number of closes is below the number of opens.
  5. 5. How many strings does generate_parentheses(4) return?

    The counts are the Catalan numbers 1, 2, 5, 14, 42, ... so four pairs give 14 well-formed strings.

Summary

  • Backtracking builds a solution step by step and undoes each step, which is a depth-first walk over a search tree.
  • Template: goal test, loop over choices, skip invalid ones (pruning), choose, recurse, undo.
  • Store copies of mutable state when you record a result.
  • Pruning (early constraint checks, sorted breaks) can shrink the tree dramatically without changing the answers.
  • Backtracking is exponential in the worst case; use it for small inputs or strongly pruned searches.
  • Related lessons: Subsets, Permutations and Combinations, N-Queens, Sudoku and Constraint Puzzles.

Next: Subsets, Permutations and Combinations