Backtracking Problems Guide for LeetCode Interviews

Every time an interviewer asks you to generate all permutations, find every valid combination, or solve a constraint satisfaction puzzle like Sudoku, the answer is the same pattern: backtracking. It appears more frequently than most candidates expect — across subsets, partitioning, board games, and string problems — and once you learn the template, these problems stop feeling intimidating.

Leetcode backtracking problems share a common structure. You build a candidate solution one decision at a time, explore deeper when the partial solution is still valid, and undo your last choice when you hit a dead end. This "DFS with undo" mental model is the key insight that transforms a confusing recursion problem into a mechanical process.

This guide walks you through the backtracking algorithm from first principles, gives you the universal template, and applies it to the most common interview problems: Subsets, Combination Sum, Permutations, N-Queens, and more. By the end, you will have a reliable framework for tackling any backtracking problem you encounter.

Backtracking is a refinement of depth-first search. In plain DFS, you explore all paths in a tree or graph. In backtracking, you explore a decision tree — a tree where each node represents a choice you make while building a solution — and you prune branches that cannot possibly lead to a valid answer. The "undo" step is what makes it backtracking rather than plain recursion: after exploring one branch, you reverse your last choice and try the next option.

Think of it as navigating a maze. At each fork, you pick a direction and walk forward. If you hit a dead end, you walk back to the fork and try a different direction. You never explore a path you already know leads nowhere. The decision tree mental model is critical: the root is an empty solution, each level adds one more decision, and the leaves are complete candidates that you either accept or reject.

When should you reach for backtracking? Look for these signals in the problem statement: "generate all," "find every valid," "list all possible," or any problem that asks for permutations, combinations, subsets, or placements under constraints. If the problem asks for just one solution or an optimal value, backtracking might still work but dynamic programming or greedy approaches are often better.

The power of the backtracking algorithm lies in its consistency. Virtually every backtracking problem follows the same three-step loop inside a recursive function: choose an option from the available candidates, explore by recursing with that choice added to your partial solution, and un-choose by removing that option so the next iteration starts clean. This choose-explore-unchoose pattern is the template you should internalize.

The recursive function typically takes the current state (your partial solution), the remaining candidates, and any constraints. The base case checks whether the partial solution is complete — if it is, you record it as a valid answer. Otherwise, you loop through the available choices, make one, recurse, and then undo it. The undo step is essential: without it, choices from one branch leak into the next.

In pseudocode, the template looks like this. Define backtrack(state, choices). If state is a complete solution, add it to results and return. For each choice in choices: add choice to state, call backtrack with the updated state and remaining choices, then remove choice from state. That is the entire framework. The only things that change between problems are what "state" looks like, what "choices" are available, and what "complete" means.

Once you have this template memorized, solving a new backtracking problem reduces to answering three questions: What does my state represent? What are my choices at each step? What is my base case? The code follows directly from the answers.

Subsets (#78) is the simplest backtracking problem and the best place to start. Given an array of unique integers, return all possible subsets. The decision tree has one level per element, and at each level you make a binary choice: include this element or skip it. The base case is reaching the end of the array, at which point you record the current subset. This produces exactly 2^n subsets, which is the expected output size.

Combination Sum (#39) adds a constraint: given candidate numbers and a target, find all unique combinations that sum to the target. The decision tree is similar but instead of include-or-skip, you can include a candidate multiple times (since reuse is allowed). The pruning condition is straightforward — if the running sum exceeds the target, stop exploring that branch. Sorting the candidates first makes this pruning even more effective because once one candidate is too large, all subsequent ones are too.

Combinations (#77) asks for all combinations of k numbers chosen from 1 to n. This is a constrained subset problem — you build subsets but only record them when their size equals k. The pruning opportunity here is that if you have fewer remaining numbers than spots to fill, you can skip that entire branch. This kind of early termination is what separates an efficient backtracking solution from a brute-force one.

These three problems share the same skeleton. The state is a list being built up, the choices are which elements to include next, and the base case is either reaching the end of the input or hitting a size or sum target. Master them and you have the foundation for every harder backtracking problem.

Permutations (#46) is the canonical backtracking problem that interviewers love. Given an array of distinct integers, return all possible orderings. Unlike subsets where you choose to include or skip, permutations require using every element exactly once — the question is the order. The state is a permutation being built, and the choices at each step are all elements not yet used. A boolean visited array tracks which elements are available.

The key difference from subset problems is that permutations care about order. [1, 2, 3] and [3, 2, 1] are different permutations but the same subset. This means the branching factor at each level is the number of unused elements, giving O(n!) total permutations. The base case is when the permutation length equals the input length.

N-Queens (#51) elevates backtracking to constraint satisfaction. Place n queens on an n x n chessboard so that no two queens attack each other. You place one queen per row, choosing which column to put her in. The backtracking template is identical: choose a column, check if it conflicts with already-placed queens (same column, same diagonal), and if valid, recurse to the next row. If no column works, backtrack to the previous row and try a different column.

Sudoku Solver (#37) follows the same constraint satisfaction pattern. Find an empty cell, try digits 1-9, check row/column/box constraints, recurse, and undo if no digit works. The decision tree is deep (up to 81 levels) but aggressive pruning — checking constraints immediately after each placement — keeps the solution fast enough. These problems prove that the backtracking template scales from simple enumeration to complex puzzle solving.

Raw backtracking without pruning is just brute-force enumeration, and it can easily explode to O(n!) or O(2^n) time. Pruning is what makes backtracking practical. The idea is simple: before recursing into a branch, check whether that branch can possibly lead to a valid solution. If not, skip it entirely. Every skipped branch saves exponential work because you avoid the entire subtree below it.

Sorting the input is the most common and effective pruning technique. In Combination Sum (#39), sorting candidates lets you break out of the loop as soon as a candidate exceeds the remaining target — every candidate after it is even larger. In Subsets II (#90) and Combination Sum II (#40), sorting lets you skip duplicate elements by comparing each candidate to the previous one at the same decision level.

For constraint satisfaction problems like N-Queens, maintaining auxiliary data structures dramatically speeds up validity checks. Instead of scanning the board for conflicts on every placement, track which columns and diagonals are occupied using sets or boolean arrays. Checking set membership is O(1) versus O(n) for scanning, and since this check runs at every node in the decision tree, the savings compound multiplicatively.

A practical rule of thumb: if your backtracking solution gets Time Limit Exceeded, first check whether you are pruning at all. Then check whether you can sort the input to enable earlier pruning. Finally, look for ways to make your constraint checks O(1) with precomputed lookup structures. These three steps resolve the vast majority of TLE issues in backtracking problems.

Backtracking is one of those patterns where the template is easy to understand but hard to apply under pressure. The gap between reading about choose-explore-unchoose and confidently implementing it in 20 minutes during an interview is filled by deliberate, spaced practice. You need to solve enough problems that the template becomes automatic and your mental energy goes to modeling the problem, not remembering the recursion structure.

Start with the gateway problems: Subsets (#78) and Combination Sum (#39). These are the simplest applications of the template and let you focus on getting the recursion right without complex constraints. Once those feel easy, move to Permutations (#46) to practice the visited-array variation, then tackle N-Queens (#51) to handle constraint satisfaction. This progression builds each skill on the previous one.

YeetCode flashcards are built for exactly this kind of pattern drilling. Each backtracking problem is distilled into a flashcard that tests whether you can identify the problem type, recall the template variation, and spot the pruning opportunity. Spaced repetition ensures you revisit problems at increasing intervals, cementing the pattern into long-term memory rather than short-term cramming.

The end goal is pattern recognition on sight. When you see a problem that says "generate all valid combinations" or "find every arrangement that satisfies these constraints," your brain should immediately map it to the backtracking template, identify the state and choices, and start coding. That level of fluency comes from consistent, well-timed review — and it is the difference between struggling through a backtracking problem and solving it confidently.