Recursion & Backtracking

// General Backtracking Template
void backtrack(State state, List<Result> results) {
    // 1. Check if we've found a valid solution
    if (isGoal(state)) {
        results.add(copy(state.solution));
        return;
    }
    
    // 2. Try each possible choice
    for (Choice choice : getChoices(state)) {
        // 3. Skip invalid choices (pruning)
        if (!isValid(choice, state)) continue;
        
        // 4. Make the choice
        state.make(choice);
        
        // 5. Explore with this choice
        backtrack(state, results);
        
        // 6. Undo the choice (backtrack)
        state.undo(choice);
    }
}

// Key Pattern: Choose → Explore → Unchoose
// - Choose: Add current element to path
// - Explore: Recurse to next decision point
// - Unchoose: Remove element to try other options

                         []  ← Start with empty set
                        / \
              Include 1?  Skip 1?
                      /       \
                   [1]         []
                  /   \       /   \
        Include 2?  Skip 2?  Include 2?  Skip 2?
              /        \        /          \
           [1,2]      [1]      [2]         []
             ✓         ✓        ✓           ✓

  All Subsets: [], [1], [2], [1,2]
  
   At each node, we CHOOSE to include or skip,
     EXPLORE both paths, then UNCHOOSE (backtrack) to parent!

// Subsets - All possible subsets of array
// Time: O(2^n), Space: O(n)
List> subsets(int[] nums) {
    List> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

void backtrack(int[] nums, int start, List path, 
               List> result) {
    // Every path is a valid subset
    result.add(new ArrayList<>(path));
    
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);              // Choose
        backtrack(nums, i + 1, path, result);  // Explore
        path.remove(path.size() - 1);   // Unchoose
    }
}

// Subsets II (with duplicates) - Skip duplicates
List> subsetsWithDup(int[] nums) {
    List> result = new ArrayList<>();
    Arrays.sort(nums);  // Sort to group duplicates
    backtrackDup(nums, 0, new ArrayList<>(), result);
    return result;
}

void backtrackDup(int[] nums, int start, List path, 
                  List> result) {
    result.add(new ArrayList<>(path));
    
    for (int i = start; i < nums.length; i++) {
        // Skip duplicates at same level
        if (i > start && nums[i] == nums[i - 1]) continue;
        
        path.add(nums[i]);
        backtrackDup(nums, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

// Combinations - Choose k elements from n
List> combine(int n, int k) {
    List> result = new ArrayList<>();
    backtrackCombine(n, k, 1, new ArrayList<>(), result);
    return result;
}

void backtrackCombine(int n, int k, int start, List path, 
                      List> result) {
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    
    // Pruning: need k-path.size() more elements
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        backtrackCombine(n, k, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

// Combination Sum - Elements can be reused
List> combinationSum(int[] candidates, int target) {
    List> result = new ArrayList<>();
    backtrackSum(candidates, target, 0, new ArrayList<>(), result);
    return result;
}

void backtrackSum(int[] candidates, int remain, int start, 
                  List path, List> result) {
    if (remain == 0) {
        result.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remain) continue;
        
        path.add(candidates[i]);
        // i (not i+1) allows reuse of same element
        backtrackSum(candidates, remain - candidates[i], i, path, result);
        path.remove(path.size() - 1);
    }
}

// Permutations - All orderings
// Time: O(n!), Space: O(n)
List> permute(int[] nums) {
    List> result = new ArrayList<>();
    backtrackPermute(nums, new ArrayList<>(), new boolean[nums.length], result);
    return result;
}

void backtrackPermute(int[] nums, List path, boolean[] used, 
                      List> result) {
    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]);
        backtrackPermute(nums, path, used, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

// Permutations II (with duplicates)
List> permuteUnique(int[] nums) {
    List> result = new ArrayList<>();
    Arrays.sort(nums);  // Sort to handle duplicates
    backtrackUnique(nums, new ArrayList<>(), new boolean[nums.length], result);
    return result;
}

void backtrackUnique(int[] nums, List path, boolean[] used, 
                     List> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        
        // Skip duplicates: if previous same element wasn't used at this level
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        
        used[i] = true;
        path.add(nums[i]);
        backtrackUnique(nums, path, used, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

// Letter Combinations of Phone Number
List letterCombinations(String digits) {
    if (digits.isEmpty()) return new ArrayList<>();
    
    String[] mapping = {"", "", "abc", "def", "ghi", "jkl", 
                        "mno", "pqrs", "tuv", "wxyz"};
    List result = new ArrayList<>();
    backtrackLetters(digits, 0, new StringBuilder(), mapping, result);
    return result;
}

void backtrackLetters(String digits, int index, StringBuilder path, 
                      String[] mapping, List result) {
    if (index == digits.length()) {
        result.add(path.toString());
        return;
    }
    
    String letters = mapping[digits.charAt(index) - '0'];
    for (char c : letters.toCharArray()) {
        path.append(c);
        backtrackLetters(digits, index + 1, path, mapping, result);
        path.deleteCharAt(path.length() - 1);
    }
}

N-Queens Problem

// N-Queens - Place N queens on NxN board
List> solveNQueens(int n) {
    List> result = new ArrayList<>();
    char[][] board = new char[n][n];
    
    for (char[] row : board) Arrays.fill(row, '.');
    
    backtrackQueens(board, 0, result);
    return result;
}

void backtrackQueens(char[][] board, int row, List> result) {
    if (row == board.length) {
        result.add(constructBoard(board));
        return;
    }
    
    for (int col = 0; col < board.length; col++) {
        if (isValidQueen(board, row, col)) {
            board[row][col] = 'Q';
            backtrackQueens(board, row + 1, result);
            board[row][col] = '.';
        }
    }
}

boolean isValidQueen(char[][] board, int row, int col) {
    // Check column above
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    
    // Check upper-left diagonal
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    
    // Check upper-right diagonal
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    
    return true;
}

List constructBoard(char[][] board) {
    List result = new ArrayList<>();
    for (char[] row : board) {
        result.add(new String(row));
    }
    return result;
}

Sudoku Solver

// Sudoku Solver
void solveSudoku(char[][] board) {
    solve(board);
}

boolean solve(char[][] board) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == '.') {
                for (char c = '1'; c <= '9'; c++) {
                    if (isValidSudoku(board, row, col, c)) {
                        board[row][col] = c;
                        
                        if (solve(board)) return true;
                        
                        board[row][col] = '.';  // Backtrack
                    }
                }
                return false;  // No valid digit found
            }
        }
    }
    return true;  // All cells filled
}

boolean isValidSudoku(char[][] board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        // Check row
        if (board[row][i] == c) return false;
        // Check column
        if (board[i][col] == c) return false;
        // Check 3x3 box
        int boxRow = 3 * (row / 3) + i / 3;
        int boxCol = 3 * (col / 3) + i % 3;
        if (board[boxRow][boxCol] == c) return false;
    }
    return true;
}

Solidify your recursion and backtracking skills with these classic problems!