Explore all possibilities by building solutions incrementally and abandoning paths that can't lead to valid solutions.
Backtracking is DFS + pruning. You build a solution one step at a time. At each step you try all available options. If the current path cannot lead to a valid solution, you backtrack — undo the last choice and try the next option.
Every backtracking problem can be visualized as a tree of choices. Each node represents a partial solution. Branches represent adding a new choice. Leaf nodes are complete solutions (or dead ends that get pruned).
Think of it as a maze. You walk forward, making choices at each fork. When you hit a dead end, you walk backward (backtrack) to the last fork and try a different direction. Without pruning, this is brute-force DFS. With pruning, you skip entire hallways you know lead nowhere.
Look for these recognition signals in the problem statement. If you spot one, backtracking is very likely the intended approach.
"Generate all" / "Find all possible"
Constraint satisfaction
Path finding with constraints
Exhaustive enumeration
Backtracking vs. DP: Both explore subproblems recursively. Use DP when subproblems overlap and you only need an optimal value. Use backtracking when you need to enumerate all solutions or when the state space has no useful overlapping subproblems.
Nearly every backtracking problem follows this universal three-phase template: choose, explore, unchoose.
void backtrack(List<Integer> path, int[] choices, int start) { if (isComplete(path)) { result.add(new ArrayList<>(path)); // save a copy return; } for (int i = start; i < choices.length; i++) { if (!isValid(choices[i])) continue; // prune path.add(choices[i]); // 1. CHOOSE backtrack(path, choices, i + 1); // 2. EXPLORE path.remove(path.size() - 1); // 3. UNCHOOSE } }
Add the current option to your partial solution. This moves you deeper into the decision tree.
Recursively explore all possibilities that build on this choice. This is the DFS step.
Remove the choice to restore state. This is the backtrack — moving back up the tree to try the next branch.
Why copy the path? In result.add(new ArrayList<>(path)) we create a snapshot because path is mutated in place. Without the copy, every entry in result would point to the same (eventually empty) list.
Generate all subsets (the power set) of [1, 2, 3]. At each element, you have two choices: include it or skip it. Every node in the tree is a valid subset.
At each level, we decide whether to include the next element. Every path from root to any node is a valid subset.
Every leaf is a subset. Total: 23 = 8 subsets. In the code, we collect the path at every recursive call (not just at the leaves).
List<List<Integer>> result = new ArrayList<>(); void subsets(int[] nums) { backtrack(nums, 0, new ArrayList<>()); } void backtrack(int[] nums, int start, List<Integer> path) { result.add(new ArrayList<>(path)); // every path is a valid subset for (int i = start; i < nums.length; i++) { path.add(nums[i]); // choose backtrack(nums, i + 1, path); // explore path.remove(path.size() - 1); // unchoose } }
Key difference from permutations: Subsets use a start index to avoid duplicates. Element [1,2] and [2,1] are the same subset, so we only ever pick elements that come after the current index.
Generate all permutations of [1, 2, 3]. Unlike subsets, order matters: [1,2,3] and [3,2,1] are different. At each level we can pick any unused element.
3 choices at level 1 × 2 at level 2 × 1 at level 3 = 3! = 6 permutations.
void backtrack(int[] nums, List<Integer> path, boolean[] used) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; // skip already-used used[i] = true; // choose path.add(nums[i]); backtrack(nums, path, used); // explore path.remove(path.size() - 1); // unchoose used[i] = false; } }
No start index here. Unlike subsets, permutations always loop from index 0 because order matters. Instead, we use a used[] boolean array to track which elements are already in the current path.
Find all combinations from [2, 3, 6, 7] that sum to target = 7. Each number can be reused unlimited times. This is where pruning becomes essential.
When the running sum exceeds the target, we prune the entire subtree. Sorting the array lets us prune even earlier: once sum + candidates[i] > target, all subsequent candidates are also too large.
void backtrack(int[] cands, int target, int start, List<Integer> path) { if (target == 0) { result.add(new ArrayList<>(path)); return; } for (int i = start; i < cands.length; i++) { if (cands[i] > target) break; // prune: sorted, so all later > target too path.add(cands[i]); // choose backtrack(cands, target - cands[i], i, path); // explore (i, not i+1: reuse allowed) path.remove(path.size() - 1); // unchoose } }
Notice the break, not continue. Because the array is sorted, once cands[i] > target, every element after it is also too large. We can skip the entire rest of the loop. This is the power of sorting + pruning.
Pruning is what separates practical backtracking from impractical brute force. The more branches you can eliminate early, the faster your algorithm runs.
Explore every branch to its leaf, even when the sum already exceeds the target.
Sort first, then break as soon as current candidate exceeds remaining target.
candidates[i] > remaining, use break instead of continue to skip all larger elements at once.if (i > start && nums[i] == nums[i-1]) continue;boolean[] used array prevents picking the same element twice. This eliminates invalid branches immediately.Rule of thumb: Always ask "can I reject this branch early?" before recursing. Sorting costs O(n log n) but can turn an exponential search into something much more tractable by pruning entire subtrees.
These classic LeetCode problems use backtracking. They are listed in rough order of difficulty within each category.
Practice tip: Start with #78 (Subsets) and #46 (Permutations) to internalize the template. Then tackle #39 (Combination Sum) to learn pruning. Once comfortable, #51 (N-Queens) is the ultimate constraint-satisfaction backtracking problem.
Enter an array of numbers and step through the subset generation. Watch the backtracking algorithm build the decision tree, collect results, and backtrack when needed.
Backtracking complexity varies dramatically depending on the problem type. Here are the three fundamental cases:
Subsets: Each of the n elements has 2 choices (in or out), giving 2n total subsets. Even the optimal algorithm must at least enumerate all of them. Time: O(n * 2n) because each subset takes O(n) to copy.
Permutations: n choices for position 1, n-1 for position 2, etc. Total: O(n * n!) including the copy step.
Space: O(n) for the recursion stack depth (the path and the call stack), plus O(answer_size) for storing all results.
Pruning does not change the worst case but it often dramatically reduces the average case. In practice, a well-pruned backtracking solution runs orders of magnitude faster than the theoretical worst case.
Choose → Explore → Unchoose. This three-phase template is the skeleton of every backtracking solution. Memorize it. The only things that change between problems are what "choose" means and what "complete" means.
Pruning is the differentiator. Without pruning, backtracking is just brute-force DFS. Sort the input, skip duplicates, and check constraints early to eliminate entire subtrees before wasting time exploring them.
Three fundamental types. Subsets (use start index, collect at every node), Permutations (use used[] array, collect at leaves only), and Combinations (like subsets but with a target constraint). Every backtracking problem is a variation of one of these three.
Visualize the decision tree. Before writing code, draw the tree of choices. This makes it obvious what your loop variable is, when to prune, and what the base case should be. The code writes itself once you have the tree.
Do not forget to copy and restore. Two classic bugs: forgetting to copy the path before adding it to results (all results end up as the same empty list), and forgetting to undo the choice (the path grows without bound). The choose/unchoose pair must always be symmetric.