Backtracking

Backtracking is a recursive technique for exploring all possible solutions by building a solution incrementally and abandoning ("backtracking") when a partial solution cannot lead to a valid complete solution.

Real-World Analogy

Imagine solving a maze. You walk forward until you hit a dead end. When you hit a dead end, you go back to the last intersection and try a different path. You keep doing this until you find the exit.

That's backtracking — try, if it fails, undo and try something else.

The Pattern

Every backtracking problem follows this template:

void backtrack(state, choices) {
    // Base case: valid solution found
    if (isSolution(state)) {
        result.add(new ArrayList<>(state));  // Must copy!
        return;
    }
    
    // Try each choice
    for (choice : choices) {
        // 1. Choose: add choice to state
        state.add(choice);
        
        // 2. Explore: recurse with updated state
        backtrack(state, remainingChoices);
        
        // 3. Unchoose: remove choice (backtrack)
        state.remove(state.size() - 1);
    }
}

Key Insight: Why Copy the State?

// WRONG: adding reference to state
result.add(state);  // state changes later!

// RIGHT: adding a copy
result.add(new ArrayList<>(state));  // independent copy

When to Use Backtracking

Signal	Example
"Find ALL..."	Find all subsets, all permutations
"Generate all..."	Generate all valid parentheses
"Is there a..."	Is there a valid arrangement?
Constraint satisfaction	N-Queens, Sudoku
Explore and undo	Maze solving, word search

Backtracking vs Other Patterns

Pattern	Structure	Output
Recursion	Linear chain	Single answer
Backtracking	Tree exploration	All valid solutions
DFS	Graph traversal	Visit all nodes
DP	Subproblems	Optimal answer

The Three Steps

1. Choose: Make a decision (add to current state)
2. Explore: Recursively explore consequences
3. Unchoose: Undo the decision (remove from state)

This "choose-explore-unchoose" cycle is the essence of backtracking.

Pattern 1: Subsets

Generate all possible subsets of a set.

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, 
                       List<Integer> state, List<List<Integer>> result) {
    result.add(new ArrayList<>(state));
    
    for (int i = start; i < nums.length; i++) {
        state.add(nums[i]);           // Choose
        backtrack(nums, i + 1, state, result);  // Explore
        state.remove(state.size() - 1);  // Unchoose
    }
}

Time: O(2^n) — each element is either included or not.

Pattern 2: Permutations

Generate all possible orderings.

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, boolean[] used, 
                       List<Integer> state, List<List<Integer>> result) {
    if (state.size() == nums.length) {
        result.add(new ArrayList<>(state));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        
        used[i] = true;
        state.add(nums[i]);
        backtrack(nums, used, state, result);
        state.remove(state.size() - 1);
        used[i] = false;
    }
}

Time: O(n! × n) — n! permutations, each takes O(n) to copy.

Pattern 3: Combinations

Choose k items from n items.

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(n, k, 1, new ArrayList<>(), result);
    return result;
}

private void backtrack(int n, int k, int start, 
                       List<Integer> state, List<List<Integer>> result) {
    if (state.size() == k) {
        result.add(new ArrayList<>(state));
        return;
    }
    
    for (int i = start; i <= n; i++) {
        state.add(i);
        backtrack(n, k, i + 1, state, result);
        state.remove(state.size() - 1);
    }
}

Time: O(C(n,k) × k) — C(n,k) combinations.

Pattern 4: Constraint Satisfaction

N-Queens, Sudoku, etc.

// N-Queens template
private void backtrack(int row, int n, 
                       List<Integer> queens, List<List<String>> result) {
    if (row == n) {
        result.add(createBoard(queens, n));
        return;
    }
    
    for (int col = 0; col < n; col++) {
        if (isValid(queens, row, col)) {
            queens.add(col);        // Choose
            backtrack(row + 1, n, queens, result);  // Explore
            queens.remove(queens.size() - 1);  // Unchoose
        }
    }
}

Pattern Selection Guide

Pattern	Key Question	Example
Subsets	Include or exclude each item?	Subsets, Subsets II
Permutations	What order?	Permutations, Permutations II
Combinations	Which k items?	Combination Sum, Combinations
Constraint	Valid arrangement?	N-Queens, Sudoku, Word Search

Pruning means stopping early when you know a path cannot lead to a valid solution.

Why Prune?

Without pruning, backtracking explores ALL possibilities. With pruning, you skip impossible branches.

Example: Combination Sum

Find all combinations that sum to target.

// WITHOUT pruning (slower)
for (int i = start; i < candidates.length; i++) {
    state.add(candidates[i]);
    backtrack(candidates, target - candidates[i], i, state, result);
    state.remove(state.size() - 1);
}

// WITH pruning (faster)
Arrays.sort(candidates);  // Sort first!
for (int i = start; i < candidates.length; i++) {
    if (candidates[i] > target) break;  // PRUNE: no point continuing
    state.add(candidates[i]);
    backtrack(candidates, target - candidates[i], i, state, result);
    state.remove(state.size() - 1);
}

Pruning Techniques

1. Sort first: Enables early termination
2. Bound checking: If current state can't possibly lead to solution, stop
3. Feasibility check: Before choosing, verify the choice is valid
4. Symmetry breaking: Avoid exploring equivalent solutions

Example: N-Queens Pruning

private boolean isValid(List<Integer> queens, int row, int col) {
    for (int r = 0; r < row; r++) {
        int c = queens.get(r);
        if (c == col) return false;           // Same column
        if (Math.abs(r - row) == Math.abs(c - col)) return false;  // Diagonal
    }
    return true;
}

Only try columns that are valid — don't even recurse on invalid ones.

Complexity with Pruning

Problem	Without Pruning	With Pruning
N-Queens	O(n^n)	O(n!)
Combination Sum	O(2^n)	Much faster in practice
Sudoku	O(9^81)	O(1) in practice

Pruning doesn't change worst-case complexity, but dramatically improves average-case performance.

Complete Template

public class BacktrackingTemplate {
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> solve(int[] nums) {
        backtrack(nums, 0, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int[] nums, int start, List<Integer> state) {
        // Base case (if needed)
        if (/* valid solution */) {
            result.add(new ArrayList<>(state));  // COPY!
            return;
        }
        
        // Explore choices
        for (int i = start; i < nums.length; i++) {
            // Prune: skip invalid choices
            if (/* invalid */) continue;
            
            // Choose
            state.add(nums[i]);
            
            // Explore
            backtrack(nums, i + 1, state);
            
            // Unchoose
            state.remove(state.size() - 1);
        }
    }
}

Subsets Template

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    subsetsHelper(nums, 0, new ArrayList<>(), result);
    return result;
}

private void subsetsHelper(int[] nums, int start, 
                           List<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        subsetsHelper(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Permutations Template

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    permuteHelper(nums, new boolean[nums.length], new ArrayList<>(), result);
    return result;
}

private void permuteHelper(int[] nums, boolean[] used, 
                           List<Integer> current, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        
        used[i] = true;
        current.add(nums[i]);
        permuteHelper(nums, used, current, result);
        current.remove(current.size() - 1);
        used[i] = false;
    }
}

Word Search Template

public boolean exist(char[][] board, String word) {
    int m = board.length, n = board[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

private boolean dfs(char[][] board, String word, int r, int c, int index) {
    if (index == word.length()) return true;
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
    if (board[r][c] != word.charAt(index)) return false;
    
    char temp = board[r][c];
    board[r][c] = '#';  // Mark visited
    
    boolean found = dfs(board, word, r+1, c, index+1) ||
                    dfs(board, word, r-1, c, index+1) ||
                    dfs(board, word, r, c+1, index+1) ||
                    dfs(board, word, r, c-1, index+1);
    
    board[r][c] = temp;  // Unmark (backtrack)
    return found;
}