roadmap/Backtracking

Topic 9 / 16

Backtracking

HardRecursion~5 days
Challenging
progress0 / 13 solved

Build candidates incrementally and abandon ('backtrack') when a constraint is violated.

⚠️
Why this topic is hard

Backtracking is hard because the solution isn't a sequence of independent decisions — each choice constrains future choices. The recursive structure looks simple but visualizing the full decision tree takes practice. The most common mistake is not properly undoing state changes before trying the next branch — this is the literal 'back' in backtracking.

Prerequisites
← Trees
Concept

Build a solution incrementally. At each step, try all valid choices. If a choice leads to an invalid state or dead end, undo it ('backtrack') and try the next choice. The search space is a decision tree — backtracking prunes branches early to avoid exploring invalid paths.

When to use this pattern
  • ◆Generate all combinations, permutations, or subsets
  • ◆Constraint satisfaction (Sudoku, N-Queens)
  • ◆Word search in a grid
  • ◆Maze / path finding with constraints
Common patterns
Subsets
At each index, choose to include or exclude. Recurse with i+1.
Combinations
Pick k elements from n. Branch on each remaining element.
Permutations
Pick from remaining elements. Use a visited set.
Constraint propagation
Check validity at each step to prune early (Sudoku, N-Queens).
Visual walkthrough
Backtracking
Generate All Subsets
RECORD
current path (depth = 0)
[empty]
subsets found so far (1 / 8)
[∅]
Record subset: [∅]
Empty set is always a valid subset.
The "back" in backtracking: path.pop() undoes the last choice. Without this, you'd have no way to explore alternative branches.
step 1/23
Brute force → optimal thinking
Brute force
Generate all possible sequences (iteratively) — exponential without pruning.
Observation
Many paths share a prefix. Once a prefix is invalid, all paths with that prefix can be pruned.
Optimization
DFS with a `path` array. Push candidate, recurse, pop (backtrack). Add validity check at each step.
Final complexity
O(n × 2ⁿ) for subsets, O(n × n!) for permutations — inherently exponential but pruning reduces constant factor.
Quick Recall Check

What must you do after each recursive call in a backtracking solution?

How do you avoid duplicate subsets when the input has duplicate numbers?

In Combination Sum, why can you reuse the same index i in the recursive call?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Heap / Priority Queue
next
Graphs (DFS / BFS)
→
Progress is saved on this device