Pattern 10 of 18 · Search & Graphs

Backtracking

Explore, and undo — build every valid combination by pruning as you go.

Explore a decision one choice at a time, undo it if it doesn't lead anywhere, and try the next option. It's a systematic way to generate every valid combination, permutation, or arrangement.

Key concepts

  • Build a partial solution recursively, and only "commit" it once it's complete and valid.
  • After exploring a choice, undo it before trying the next one — that's what turns the search into a tree instead of a single path.
  • Pruning: stop exploring a branch as soon as you know it can't lead to a valid answer.

When to use it

  • The problem asks for "all possible" combinations, subsets, permutations, or valid arrangements.
  • A greedy or direct-formula approach doesn't work because you genuinely need to explore multiple branches.

Tips

  • Write the base case (when a candidate solution is complete) before the recursive case.
  • Pruning early is the difference between backtracking that finishes instantly and one that times out.
  • Sort the input first when the problem needs to skip duplicates (e.g. "no duplicate combinations").

Practice problems (9)

Blind 75 (2):

More from Blind 150 (7):

← Heap / Priority QueueGraphs →

See the full roadmap →