Backtracking Fundamentals — Exploring All Possibilities
Master the backtracking pattern by learning when to explore paths, how to prune invalid branches, and why state management is critical.
Problem Statement
Backtracking problems require exploring all possible solutions by building candidates incrementally and abandoning them as soon as they fail constraints. Understanding the core template and state management patterns is essential for solving permutations, combinations, subsets, and constraint satisfaction problems.
Why This Problem Matters
- Backtracking appears in 15-20% of medium-hard interview problems, including permutations, N-Queens, Sudoku solver, and combination sum.
- It tests your ability to manage recursive state, prune search spaces, and articulate time/space complexity for exponential algorithms.
- Mastering backtracking prepares you for dynamic programming by building intuition for optimal substructure and overlapping subproblems.
Thought Process
Recognize the exploration pattern
If the problem asks for all combinations, permutations, subsets, or valid configurations, suspect backtracking. The key signal is needing to explore multiple paths and potentially backtrack when a path violates constraints.
Define your state and choices
Identify what needs to be tracked in your recursive state (current path, remaining choices, position). Each recursive call represents making one choice, and backtracking means undoing that choice to try alternatives.
Implement pruning conditions
Add early termination checks to avoid exploring invalid branches. For example, if building permutations of distinct numbers, skip duplicates. If solving N-Queens, check if placing a queen attacks existing queens before recursing deeper.
Step-by-Step Reasoning
- Define base case: When should you add the current path to results? Usually when you reach target length or exhaust choices.
- Loop through choices: At each level, iterate through available options (remaining numbers, positions, etc.).
- Make choice: Add current choice to path or mark as used.
- Recurse: Call backtrack function with updated state (reduced choices, advanced position).
- Undo choice: Remove from path or unmark — this is the backtracking step that allows exploring other branches.
- Return all collected results after exploring all paths.
Dry Run
Input: Generate all permutations of [1, 2, 3]
Start with empty path []. At level 0, try adding 1: path becomes [1]. Recurse. At level 1, try adding 2: path becomes [1,2]. Recurse. At level 2, try adding 3: path becomes [1,2,3]. Base case reached, save result. Backtrack: remove 3, path is [1,2]. No more choices at this level. Backtrack: remove 2, path is [1]. Try adding 3: path becomes [1,3]. Recurse and continue this pattern until all 6 permutations are generated.
Input: Generate all subsets of [1, 2, 3]
Start with empty subset []. At each element, make two choices: include it or skip it. For 1: include → [1], skip → []. For each branch, process element 2, then 3. This generates 2³ = 8 subsets: [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3].
Complexity Analysis
Time
O(b^d) where b is branching factor and d is depth
Space
O(d) for recursion stack
Why
Backtracking explores decision trees. For permutations of n items: O(n!). For subsets: O(2^n). For combinations: O(C(n,k) * k). Space depends on recursion depth, typically O(n) for most problems.
Annotated Solution
import java.util.ArrayList;
import java.util.List;
public class Backtracking {
// Template: Generate all permutations
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
return result;
}
private void backtrack(
List<List<Integer>> result,
List<Integer> path,
int[] nums,
boolean[] used
) {
// Base case: collected all numbers
if (path.size() == nums.length) {
result.add(new ArrayList<>(path)); // Must copy!
return;
}
// Try each number
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // Skip if already in path
// Make choice
path.add(nums[i]);
used[i] = true;
// Recurse
backtrack(result, path, nums, used);
// Undo choice (backtrack)
path.remove(path.size() - 1);
used[i] = false;
}
}
// Template: Generate all subsets
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, 0);
return result;
}
private void backtrack(
List<List<Integer>> result,
List<Integer> path,
int[] nums,
int start
) {
// Add current subset to results
result.add(new ArrayList<>(path));
// Explore adding each remaining element
for (int i = start; i < nums.length; i++) {
path.add(nums[i]); // Choose
backtrack(result, path, nums, i + 1); // Explore
path.remove(path.size() - 1); // Unchoose
}
}
}Both templates follow the choose-explore-unchoose pattern. Permutations use a boolean array to track which elements are used. Subsets use a start index to avoid revisiting earlier elements. The key is always copying the path when adding to results, and properly undoing the choice to explore other branches.
Common Pitfalls
- Forgetting to copy the path when adding to results, causing all results to reference the same modified list.
- Not undoing the choice (backtracking step), which corrupts state for subsequent branches.
- Off-by-one errors in loop bounds or start index, leading to missed or duplicate solutions.
- Inefficient pruning that allows exploring clearly invalid branches unnecessarily.
Follow-Up Questions
- How would you modify the permutation template to handle duplicate elements? (Sort input, skip consecutive duplicates when same number appears twice.)
- What changes if you need to generate combinations of exactly k elements? (Add size constraint in base case.)
- How does backtracking relate to dynamic programming? (DP optimizes overlapping subproblems; backtracking explores independent branches.)