DSA Notes
Master the backtracking algorithmic paradigm — understand state-space trees, pruning strategies, and how backtracking systematically explores solution spaces.
What is Backtracking?
Imagine you are navigating a maze. At every fork, you pick a direction and keep walking. If you hit a dead end, you retrace your steps to the last fork and try a different path. That mental model *is* backtracking — a systematic way of exploring all possible configurations by building solutions incrementally and abandoning ("pruning") a partial solution the moment you detect it cannot possibly lead to a valid answer.
Formally, backtracking is a depth-first search over a state-space tree. Each node represents a partial candidate solution, and each edge represents a decision (e.g., "place a queen in column 3"). Leaves are either complete valid solutions or dead ends where constraints are violated.
Backtracking vs Brute Force
Brute force generates *every* possible combination and checks validity at the end. Backtracking is smarter — it checks constraints as it builds the solution. The moment a partial candidate violates a constraint, the algorithm *prunes* that entire subtree, avoiding millions of useless explorations.
Consider placing 8 queens on a chessboard. Brute force examines all 64^8 ≈ 2.8 × 10^14 placements. Backtracking with column-per-row constraint reduces this to 8! = 40,320 candidates, and pruning trims it further to roughly 15,000 nodes visited.
The State-Space Tree
Every backtracking algorithm implicitly builds a tree:
- Root: Empty candidate (no decisions made yet)
- Internal nodes: Partial solutions
- Edges: One choice at the current decision point
- Leaves: Complete solutions or pruned dead ends
A pruning function (often called is_safe or is_valid) evaluates a node *before* descending into its children. If it returns false, the entire subtree is skipped.
Generic Backtracking Template
Here is the universal template that underlies virtually every backtracking problem:
def backtrack(candidate, decisions):
if is_complete(candidate):
process_solution(candidate)
return
for choice in get_choices(candidate, decisions):
if is_valid(candidate, choice):
make_choice(candidate, choice) # commit
backtrack(candidate, decisions) # recurse
undo_choice(candidate, choice) # backtrack (undo)The three critical operations are:
- Make choice — extend the partial solution
- Recurse — move deeper into the tree
- Undo choice — restore state so the next sibling branch starts clean
Dry Run: Generating Permutations of [1, 2, 3]
Let us trace the algorithm on a small example:
| ├── choose 1 | backtrack([1], [2,3]) |
| │ ├── choose 2 | backtrack([1,2], [3]) |
| │ │ └── choose 3 | [1,2,3] ✓ SOLUTION |
| │ └── choose 3 | backtrack([1,3], [2]) |
| │ └── choose 2 | [1,3,2] ✓ SOLUTION |
| ├── choose 2 | backtrack([2], [1,3]) |
| │ ├── choose 1 | backtrack([2,1], [3]) |
| │ │ └── choose 3 | [2,1,3] ✓ SOLUTION |
| │ └── choose 3 | backtrack([2,3], [1]) |
| │ └── choose 1 | [2,3,1] ✓ SOLUTION |
| └── choose 3 | backtrack([3], [1,2]) |
| ├── choose 1 | backtrack([3,1], [2]) |
| │ └── choose 2 | [3,1,2] ✓ SOLUTION |
| └── choose 2 | backtrack([3,2], [1]) |
| └── choose 1 | [3,2,1] ✓ SOLUTION |
All 3! = 6 permutations are generated. If we added a constraint (say, "1 never immediately follows 3"), some branches would be pruned.
Complete Python Implementation
C++ Implementation
Time and Space Complexity
| Aspect | Complexity | Notes |
|---|---|---|
| Worst-case time | O(n!) or O(2^n) | Depends on branching factor and depth |
| Best-case time | O(1) | If pruning eliminates early |
| Space (recursion stack) | O(n) | Depth of the state-space tree |
| Space (storing solutions) | O(n × k) | k = number of valid solutions |
Backtracking does not improve worst-case complexity over brute force — but in practice, aggressive pruning reduces explored nodes by orders of magnitude.
Pruning Strategies
- Constraint checking — reject immediately if a constraint is violated (e.g., two queens attack each other)
- Bound checking — if a partial solution cannot possibly beat the current best, prune (branch and bound)
- Symmetry breaking — avoid exploring mirror-image configurations
- Ordering heuristics — try the most constrained variable first (fail-fast)
When to Use Backtracking
Backtracking excels when:
- The problem asks for all solutions or any one valid configuration
- Constraints can be checked incrementally on partial solutions
- The search space is large but heavily constrained (lots of pruning opportunities)
Classic examples: N-Queens, Sudoku, graph coloring, Hamiltonian paths, subset/permutation generation, crossword puzzles, and constraint satisfaction problems.
Real-World Applications
- Compiler design: Register allocation via graph coloring
- AI/Game solvers: Chess engines, puzzle solvers (Sudoku apps)
- Bioinformatics: Protein folding, sequence alignment
- Operations research: Scheduling, resource allocation
- Cryptography: Solving constraint systems
Summary
Backtracking = DFS + pruning. You build solutions one decision at a time, check constraints early, and undo choices that lead nowhere. The generic template (choose → recurse → unchoose) applies to hundreds of problems. Master it, and you unlock an entire category of interview and competition questions.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Backtracking Fundamentals.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, backtracking, introduction, backtracking fundamentals
Related Data Structures & Algorithms Topics