What is Backtracking?
Learn how backtracking prunes invalid branches during search, with N-Queens code and common interview pitfalls explained.
Expected Interview Answer
Backtracking is a systematic search technique that builds a solution incrementally, one choice at a time, and abandons ("backtracks" from) any partial path as soon as it can no longer possibly lead to a valid solution, rather than exploring it to completion.
It works like depth-first search over a tree of partial solutions: at each node you make a choice, recurse deeper, and if a constraint is violated or a dead end is reached, you undo the last choice and try the next option. This pruning is what separates backtracking from brute force — invalid branches are cut early instead of being fully explored. Classic use cases include N-Queens, Sudoku solving, generating permutations/subsets, and constraint satisfaction problems, where the worst case is still exponential but pruning makes it practical.
- Prunes invalid branches early instead of brute-forcing every possibility
- Naturally expressed with simple recursion and an undo step
- Solves constraint-satisfaction problems like N-Queens and Sudoku
- Generalizes to permutations, subsets, and combinatorial search
AI Mentor Explanation
A team selector tries fielding a particular player at a position, then checks if the resulting formation still satisfies all balance rules; if it does not, she immediately removes that player and tries the next candidate instead of finishing the whole lineup first. This is backtracking: commit to a choice, test it as early as possible, and undo it the moment it clearly cannot lead to a valid eleven, rather than building out every full lineup to check at the end.
Step-by-Step Explanation
Step 1
Choose
Pick a candidate value for the current decision point in the partial solution.
Step 2
Constrain
Check whether this choice still satisfies all problem constraints given prior choices.
Step 3
Recurse or reject
If valid, recurse to the next decision point; if invalid, reject this choice immediately (pruning).
Step 4
Backtrack
When a branch is exhausted or fails, undo the last choice and try the next candidate at that level.
What Interviewer Expects
- A working recursive implementation with an explicit undo step
- Clear explanation of pruning and why it beats brute force in practice
- A concrete example solved end-to-end (N-Queens, subsets, or permutations)
- Discussion of worst-case exponential time despite pruning
Common Mistakes
- Forgetting to undo (backtrack) state after a recursive call returns, causing state to leak between branches
- Not pruning early enough, effectively degrading to brute force
- Confusing backtracking with dynamic programming when subproblems do not overlap
- Mutating shared state without copying when appending a valid partial solution to results
Best Answer (HR Friendly)
“Backtracking is a way to search for a solution by building it up choice by choice, and immediately abandoning any path the moment it clearly cannot work, instead of following it all the way to the end. It is how you solve puzzles like Sudoku or generate all valid arrangements efficiently, by cutting off dead ends early.”
Code Example
def solve_n_queens(n):
solutions = []
columns = set()
diag1 = set()
diag2 = set()
placement = []
def backtrack(row):
if row == n:
solutions.append(placement.copy())
return
for col in range(n):
if col in columns or (row - col) in diag1 or (row + col) in diag2:
continue
columns.add(col)
diag1.add(row - col)
diag2.add(row + col)
placement.append(col)
backtrack(row + 1)
columns.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
placement.pop()
backtrack(0)
return solutionsFollow-up Questions
- How does backtracking differ from plain brute-force recursion?
- How would you solve Sudoku using backtracking?
- What is the worst-case time complexity of N-Queens backtracking?
- How does backtracking relate to depth-first search on a decision tree?
MCQ Practice
1. What is the defining feature of backtracking compared to brute force?
Backtracking abandons a partial solution as soon as it is known to be invalid, cutting off unnecessary exploration.
2. In the N-Queens backtracking solution, what must happen after a recursive call returns?
Undoing the last choice (removing it from columns/diagonals/placement) is essential so sibling branches are explored correctly.
3. Which problem is a classic backtracking use case?
Sudoku requires trying digit placements and undoing them when constraints are violated — a textbook backtracking problem.
Flash Cards
What does backtracking do when a partial solution fails a constraint? — It abandons that path immediately and undoes the last choice, rather than exploring it further.
What search strategy is backtracking built on? — Depth-first search over a tree of partial solutions, with pruning.
Name a classic backtracking problem. — N-Queens, Sudoku, generating permutations/subsets, or graph coloring.
What is the worst-case time complexity class for most backtracking problems? — Exponential, though pruning makes many instances practical.