What Is Backtracking?
Backtracking is a systematic way to explore all possible solutions and abandon paths that can't lead to a valid answer. Think of navigating a maze: you walk forward, hit a dead end, go back to the last fork, and try another path.
Imagine you're solving a Sudoku puzzle. You place a number in an empty cell, move to the next cell, and keep going. The moment you realize a placement violates the rules, you erase it (backtrack) and try a different number. That's backtracking: make a choice, explore it fully, and undo it if it doesn't work.
Backtracking is essentially a depth-first search over a decision tree. At each step you make a choice, recurse deeper, and — if the path fails — you undo the choice and try the next option. The "undo" step is what makes it backtracking, not just plain recursion.
The Template: Choose → Explore → Unchoose
Every backtracking problem follows the same three-step pattern. Once you recognise it, you can solve dozens of interview problems by adapting this skeleton:
Breaking it down
- Base case — Check if
pathis a complete solution. If yes, save it and return. - Choose — Pick a candidate and add it to the current path.
- Explore — Recurse with the updated path to go deeper.
- Unchoose — Remove the last choice (
path.pop()) so you can try the next candidate. This is the backtracking step.
path[:] and not just path?path directly, every entry in result points to the same list — which ends up empty after all the pop() calls. path[:] creates a snapshot (shallow copy) at the moment you found a solution.
Decision Tree for Permutations of [1, 2, 3]
Every backtracking algorithm builds a decision tree. Each node represents a partial solution; each branch represents a choice. Leaf nodes are complete permutations. Pruned branches (red, dashed) are paths we skip because the element was already used.
Permutations Decision Tree — [1, 2, 3]
At each level, we pick from the remaining elements. If an element is already in the path, we prune that branch. The 6 green leaf nodes are the 6 permutations of [1, 2, 3] — which is 3! = 6.
Problem: Permutations
Given a list of distinct integers, return all possible permutations. This is LeetCode 46 and one of the most common backtracking interview problems.
Approach: At each level of recursion, choose one element from the remaining pool. When the remaining pool is empty, you have a complete permutation.
Walk-through
- Start:
path=[],remaining=[1,2,3] - Choose 1:
path=[1],remaining=[2,3] - Choose 2:
path=[1,2],remaining=[3] - Choose 3:
path=[1,2,3],remaining=[]— save! - Unchoose 3:
path=[1,2]— back to step 3, no more choices - Unchoose 2:
path=[1]— now choose 3 instead - Choose 3:
path=[1,3],remaining=[2] - Choose 2:
path=[1,3,2]— save! ... and so on
remaining list of size up to n, so space is O(n^2) in the call stack.
Problem: Subsets
Given a list of distinct integers, return all possible subsets (the power set). This is LeetCode 78. Unlike permutations, order doesn't matter — [1,2] and [2,1] are the same subset.
Key difference: We record every partial path as a valid subset (not just complete ones). We use a start index to avoid duplicates — once we've passed an element, we don't go back to it.
How subsets differs from permutations
- Permutations: Save only when
remainingis empty (all elements used). Order matters. - Subsets: Save at every node of the tree, including the empty path. Use
startto ensure we only pick elements ahead of the current position, avoiding duplicates like [2,1] when we already have [1,2].
Problem: N-Queens (Simplified)
Place N queens on an N x N chessboard so that no two queens attack each other. Queens can attack along rows, columns, and diagonals. This is LeetCode 51 and the classic constraint satisfaction problem.
Strategy: Place one queen per row. For each row, try every column. Before placing, check that no existing queen shares the same column or diagonal. If no valid column exists for a row, backtrack to the previous row.
4-Queens Solution — One Valid Configuration
When to Use Backtracking
Backtracking is the right tool when a problem asks you to enumerate all valid configurations or find any valid configuration under constraints. Here's a quick checklist:
- Permutations — "Generate all orderings of..." (LeetCode 46)
- Combinations / Subsets — "Find all subsets / combinations that sum to..." (LeetCode 78, 39, 40)
- Constraint satisfaction — Sudoku solver, N-Queens, crossword puzzles
- Path finding with constraints — "Find all paths from source to target" (LeetCode 797)
- String partitioning — "Partition into palindromes" (LeetCode 131)
- Word search / letter board — "Find a word in a grid" (LeetCode 79)
Backtracking vs. Dynamic Programming
If the problem asks for all solutions, use backtracking. If it asks for the count or optimal value (min/max), DP might be better. Many problems can be solved with either — but backtracking enumerates, while DP optimises.
is_valid) and the base case (is_solution).
Try It Yourself
Generate All Permutations
Write a function permutations(nums) that returns all permutations of the input list. Use the Choose-Explore-Unchoose pattern.
Challenge
Given a list of distinct positive integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be used unlimited times. This is LeetCode 39.
Example: candidates = [2, 3, 6, 7], target = 7 should return [[2, 2, 3], [7]].
Hint structure: Use the subsets pattern with a start index, but instead of advancing past the current element, allow re-picking it by passing i (not i + 1) when you recurse. Add a pruning check: if the running sum exceeds the target, stop exploring.
backtrack(start, path, current_sum). Base case: if current_sum == target, save the path. Loop from start to len(candidates). For each candidate, if current_sum + candidates[i] <= target, append it to path, recurse with i (same index, allowing reuse), then pop. The start index prevents [3,2,2] appearing alongside [2,2,3].Quiz
path[:] instead of path when saving a result?You've learned to explore every possibility.
Now explore every career opportunity.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →