Topics

Backtracking: A Study Guide

Backtracking is systematic brute force with pruning. You build a candidate solution one choice at a time, and the moment a partial choice cannot lead to a valid answer, you abandon it and back up to try something else. It explores a tree of possibilities depth-first, undoing each choice as it returns. Every “generate all”, “find all”, or “does any arrangement satisfy” question is a backtracking question in disguise.

Why Backtracking Matters#

When a problem asks for all subsets, all permutations, every valid board placement, or a single arrangement that satisfies a set of constraints, there is no clever formula: you must search the space. Backtracking searches it without wasting time on branches that are already doomed. N-Queens, Sudoku, the power set, combination sum, word search, and graph coloring are all standard backtracking problems, and they teach the recursion discipline that carries into harder topics.

The Template#

Almost every backtracking solution follows the same shape:

  1. If the current state is a complete solution, record it.
  2. Otherwise, for each valid next choice: choose it, recurse, then unchoose (undo) it.

That undo step is the whole idea: it lets one mutable path object explore the entire tree without allocating a fresh copy at every node.

Complexity#

Backtracking is exponential by nature, which is why pruning matters so much:

Problem shapeRough time
All subsets of n itemsO(2^n)
All permutations of n itemsO(n!)
Constraint search (N-Queens, Sudoku)Exponential, cut down by pruning

Good pruning does not change the worst-case class, but it can turn “runs forever” into “finishes instantly” on real inputs.

A Short Example#

Generating every subset (the power set) with choose-explore-unchoose:

 1def subsets(nums):
 2    result, path = [], []
 3
 4    def backtrack(start):
 5        result.append(path[:])          # record a copy of the current path
 6        for i in range(start, len(nums)):
 7            path.append(nums[i])        # choose
 8            backtrack(i + 1)            # explore
 9            path.pop()                  # unchoose
10
11    backtrack(0)
12    return result

Common Pitfalls#

  • Forgetting to undo. Skip the pop() (or equivalent) and the path leaks state into sibling branches. This is the number-one backtracking bug.
  • Storing a reference instead of a copy. Appending path instead of path[:] stores the same list object, which later mutations overwrite.
  • Weak pruning. Without a “is this partial state still viable?” check, you explore hopeless branches and time out.
  • Duplicate results. For inputs with repeats, sort first and skip equal siblings, or you emit the same combination twice.

Where the Curriculum Covers This#

In the 60-day challenge: