Backtracking: Pruning and State-Space Trees

The Essence of Backtracking

Backtracking is an algorithmic paradigm for systematically enumerating all possible candidate solutions and reverting invalid choices.

Backtracking = Brute-force enumeration + Pruning
Backtracking = DFS traversal of a Decision Tree

At its core, backtracking is a Depth-First Search (DFS) on a State-Space Tree. When a branch is identified as "dead" (unable to yield a valid solution), the algorithm backs up to the previous node and tries a different branch.

Universal Backtracking Template

void backtrack(path, choices) {
    if (goalMet) {
        result.add(new ArrayList<>(path)); // CRITICAL: Always add a shallow copy!
        return;
    }
    
    for (choice : choices) {
        if (isInvalid(choice)) continue; // Pruning: skip invalid branches
        
        // 1. Make the choice
        path.add(choice);
        updateStatus();
        
        // 2. Recurse
        backtrack(path, newChoices);
        
        // 3. Undo the choice (The "Backtrack" step)
        path.removeLast();
        restoreStatus();
    }
}

Three Classic Problem Types

1. Permutations (Distinct Elements)

Example: Given [1, 2, 3], find all permutations.

public void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue; // Skip elements already in the current path
        
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

2. Subsets (Distinct Elements)

Example: Find all subsets of [1, 2, 3].

public void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path)); // Every node in the decision tree is a valid subset
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res); // i + 1: cannot reuse the same element
        path.remove(path.size() - 1);
    }
}

3. Combination Sum (Elements Reusable)

public void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
    if (target == 0) { res.add(new ArrayList<>(path)); return; }
    
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > target) break; // Pruning (assumes candidates is sorted)
        
        path.add(candidates[i]);
        backtrack(candidates, target - candidates[i], i, path, res); // i: can reuse current element
        path.remove(path.size() - 1);
    }
}

Handling Duplicates: "Horizontal" Pruning

When input elements repeat (e.g., [1, 1, 2]), we must ensure the same level of the tree does not process the same value twice.

// LeetCode 47: Permutations II
public void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        
        // Critical: If current is same as previous AND previous was skipped at same level
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

N-Queens: 2D Constraint Handling

void backtrack(int row, int n, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
    if (row == n) { harvestResult(); return; }
    
    for (int col = 0; col < n; col++) {
        // row - col is constant for anti-diagonal, row + col is constant for diagonal
        if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue;
        
        occupyPositions(row, col);
        backtrack(row + 1, n, cols, diag1, diag2);
        vacatePositions(row, col);
    }
}

Pruning Techniques Summary

Backtracking vs. Standard DFS

Backtracking is a specialized form of DFS focusing on Paths rather than Nodes.

Complexity Reference