Backtracking interview questions
Backtracking explores all the choices in a structured way and abandons a path as soon as it cannot work. It is the pattern behind questions that ask for every subset, arrangement or valid configuration.
How do I solve backtracking interview questions?
Backtracking builds a solution one choice at a time: choose an option, explore the rest recursively, then undo the choice and try the next. It enumerates subsets, permutations, combinations and valid placements, and pruning branches that already break a rule keeps the search from exploring everything.
How to recognise a backtracking problem
The question asks for all subsets, permutations, combinations, partitions or valid arrangements, not just a count.
A configuration must satisfy constraints, as in placing queens, filling a sudoku or finding words in a grid.
The output is expected to be large and the input small, often at most 15 to 20 items.
How to build the solution
Define the state: the choices made so far, and the position or remaining options.
Write a recursive function with a base case that records a complete solution, then a loop over the available options: choose, recurse, undo.
Prune: skip options that violate a rule, skip duplicates by sorting and not reusing the same value at one level, and stop when the remaining options cannot complete a solution.
State the cost honestly: it grows exponentially, for example 2 to the n for subsets and n factorial for permutations, so the input must be small.
Classic problems to practise
Subsets, Subsets II (with duplicates), Permutations, Combination Sum, Letter Combinations of a Phone Number, Palindrome Partitioning, N-Queens, Word Search, Generate Parentheses.
Mistakes interviewers see
Forgetting to undo the choice, so state leaks between branches. Undo exactly what you did.
Adding the working list to the results directly instead of a copy. It changes later, so every stored result ends up identical.
Generating duplicates when the input has repeated values, because sorting and the same-level skip rule are missing.
Not pruning, then arguing the exponential running time is unavoidable when a simple check would remove most branches.
Practise it as an interview
Take a topic-based interview on backtracking to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.
Frequently asked questions
What is the difference between backtracking and dynamic programming?
Backtracking enumerates solutions and undoes choices. Dynamic programming reuses answers to repeated subproblems. If you only need a count or an optimum and states repeat, prefer dynamic programming.
How do I speed up backtracking?
Prune early with constraint checks, order choices so failures appear sooner, and cache repeated states if there are any, which turns it into memoised search.