Backtracking in Coding Interviews: Subsets, Permutations, and Beyond

Backtracking questions show up constantly in technical interviews: generate all subsets, list every permutation, solve N-Queens, find all combinations that sum to a target, or search a word in a grid. They look intimidating because the output can be huge, but nearly all of them follow one template. Learn the template, and these problems become some of the most predictable in the whole interview catalog. The core idea Backtracking builds a solution step by step. At each step you choose an option, recurse to explore what follows, and then undo the choice before trying the next option. Think of it as a depth-first search over a tree of decisions. The "undo" step is what gives the technique its name. The template def backtrack(state, choices): if is_complete(state): record(state) return for choice in choices: if not valid(choice, state): continue apply(choice, state) backtrack(state, next_choices) undo(choice, state) Every problem below is a variation of where you start, what counts as complete, which choices are allowed, and how you prune. Subsets For each element, decide to include it or skip it. A neat way to code it is a start index: at each call, record the current path, then loop from start to the end, append nums[i], recurse with i + 1, and pop. There are 2^n subsets, so time is O(n * 2^n). If the input has duplicates ("Subsets II"), sort first and skip nums[i] when it equals nums[i-1] and i > start. Permutations Every position can take any unused element. Keep a used boolean array, or swap elements in place. There are n! permutations, so O(n * n!) time. With duplicates, sort and skip an element if it equals the previous one and the previous one is not used in the current path. Explaining that duplicate-skipping rule clearly is a common differentiator. Combination sum Choose numbers that add up to a target. Sort the candidates so you can stop the loop as soon as a candidate exceeds the remaining target; that is pruning. If each number can be reused, recurse with the same index; if not, recurse with i + 1. N-Queens Place one queen per row. Track used columns and both diagonals in sets (row - col and row + col identify diagonals). Constant-time validity checks make the solution fast enough for typical interview sizes. Word search in a grid Start DFS from every cell matching the first letter. Mark a cell as visited by temporarily changing its value, explore four neighbors, then restore it. That restore step is the backtracking. Prune immediately when the current letter does not match. Pruning: where performance comes from Interviewers often ask, "Can you make it faster?" The answer is usually better pruning: - Sort input to stop loops early. - Check constraints before recursing, not after. - Use sets or bitmasks for constant-time validity checks. - For word problems, use a trie to abandon prefixes that cannot match ("Word Search II"). Complexity talk Be honest that worst-case complexity is exponential because the output itself is exponential. State it in terms of output size, for example O(n * 2^n) for subsets. Mention recursion depth (usually n) as the extra space. Common bugs - Appending the path object itself instead of a copy, so every recorded answer ends up empty. - Forgetting to undo the choice. - Off-by-one errors with the start index. - Duplicate results from unsorted input. How to present it in an interview Name the pattern, sketch the decision tree for a tiny input like [1,2,3], state complexity, then code the template. Walk through one branch out loud, showing the path being built and unwound. That narration convinces interviewers you understand the mechanics rather than reciting code. Practice plan Do subsets, permutations, combination sum, palindrome partitioning, N-Queens, and word search, then revisit them a week later from a blank page. During live rounds, some candidates also use Linkjob AI (https://linkjob.ai), which gives real-time help during job interviews and technical interviews, to stay organized when they lose the thread. With the template in your head, backtracking turns from a scary category into a reliable one.