Backtracking

Backtracking explores all potential solutions by building candidates incrementally and pruning branches that can't lead to a valid solution. It's DFS with undo. Template: choose → explore → unchoose. Use for: permutations, combinations, subsets, N-Queens, Sudoku solver, word search. Time complexity is often exponential (O(2^n) or O(n!)).

Key Concepts

Deep Dive: Backtracking Template

void backtrack(result, currentPath, choices) {
    if (isComplete(currentPath)) {
        result.add(new ArrayList<>(currentPath));  // Deep copy!
        return;
    }
    for (choice : choices) {
        if (isValid(choice)) {
            currentPath.add(choice);       // Choose
            backtrack(result, currentPath, remainingChoices);  // Explore
            currentPath.removeLast();      // Unchoose (backtrack)
        }
    }
}

Deep Dive: Subsets, Permutations, Combinations

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) {
    result.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(result, path, nums, i + 1);
        path.removeLast();
    }
}

Permutations:

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(result, new ArrayList<>(), nums, used);
    return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, 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;
        used[i] = true;
        path.add(nums[i]);
        backtrack(result, path, nums, used);
        path.removeLast();
        used[i] = false;
    }
}

Combination Sum:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int remaining, int start) {
    if (remaining == 0) { result.add(new ArrayList<>(path)); return; }
    for (int i = start; i < nums.length; i++) {
        if (nums[i] > remaining) continue;  // Prune
        path.add(nums[i]);
        backtrack(result, path, nums, remaining - nums[i], i);
        path.removeLast();
    }
}

Common Interview Questions

• Subsets / Subsets II (with duplicates)
• Permutations / Permutations II
• Combination Sum I/II/III
• Letter Combinations of a Phone Number
• N-Queens
• Sudoku Solver
• Word Search
• Generate Parentheses
• Palindrome Partitioning