Backtracking Interview Questions 2026
Backtracking is algorithmic trial and error: try an option, explore recursively, undo if it leads to a dead end. The template is reusable across dozens of problems.
The Core Template
Template: def backtrack(state, choices): if is_solution(state): solutions.append(state.copy()); return; for choice in choices: if is_valid(state, choice): make_choice(state, choice); backtrack(state, next_choices(state)); undo_choice(state, choice).
The copy at collection time is critical: if you append the reference, all collected solutions will point to the same mutable object, which will be empty after backtracking finishes. Always copy.
Combinations vs Permutations
Combinations: order does not matter, elements can be used at most once (or k times). Avoid duplicates by always starting the next choice from a position after the current. Permutations: order matters, use a visited set to avoid reusing elements.
Subsets: equivalent to choosing which elements to include. Can be built with backtracking (include/exclude each element) or bit manipulation (iterate all 2^n bitmasks). Backtracking is more generalizable.
Grid and Path Problems
Word search on a grid: DFS with backtracking. Mark the cell as visited before recursing, unmark after. Prevents reusing the same cell in one path.
Maze solving, number of paths with constraints, path with specific sum: all use backtracking on the grid. Pruning: skip if current partial sum already exceeds target, or if remaining cells cannot possibly complete the word.
Constraint Satisfaction
N-Queens: place queens on an N x N board with no conflicts. State: list of column positions for each row. Constraint: no column, row, or diagonal conflict. Prune early by checking only the constraint, not by checking all placed queens.
Sudoku solver: try digits 1-9 in each empty cell, backtrack if a conflict arises. Pruning: check the row, column, and 3x3 box before placing. More advanced: minimum-remaining-values heuristic (fill the cell with fewest valid options first).
Browse Real Backtracking Questions
Actual backtracking problems from top tech company interviews.
Browse Backtracking Questions