Backtracking

Tactic

Backtracking explores a decision tree one partial candidate at a time. It chooses an option, recurses, then undoes the choice before trying the next option.

The invariant is that the current partial candidate is valid under the rules checked so far. Pruning cuts off branches as soon as they cannot lead to a complete answer.

The undo step matters. Mutating a shared list, board, or set is efficient, but every mutation needs a matching cleanup. Copying state is simpler but can add large hidden costs.

Value

The value is controlled exhaustive search. Backtracking does not magically remove exponential complexity, but it makes exponential search readable and prunable.

Direct complexity example

Brute force: Generate every raw candidate and validate only at the end: often $O(b^d \cdot d)$ time, where many branches are doomed early.
With this tactic: Validate and prune during construction: worst-case still exponential, but practical work can drop sharply.
Space: Space is $O(d)$ recursion depth plus the current candidate, not counting the output. Copy-heavy versions can use much more.

Challenges this solves

subsets and combinations
permutations
N-Queens
word search
constraint puzzles
combination sum

When to use it

Use this tactic when these conditions are true:

the problem asks for all valid arrangements or choices
each choice affects the remaining choices
invalid partial candidates can be detected early
the constraints are small enough for exponential search

When not to use it

Reach for a different tactic when these warning signs appear:

only one optimum is needed and DP or greedy can summarize the search
the branching factor and depth make exhaustive search impossible
there are repeated states that should be memoized
the problem has no natural partial validity check

Terminology clues

These prompt words often point toward this concept:

all combinations
all permutations
place
choose
valid board
search
undo
prune