Backtracking

Backtracking Overview

Backtracking is a systematic way to search through all possible configurations of a search space. It builds solutions incrementally and abandons partial solutions that cannot lead to a valid solution.

When to Use Backtracking

Exhaustive Search: Need to find all possible solutions
Constraint Satisfaction: Solutions must satisfy certain constraints
Combinatorial Problems: Permutations, combinations, subsets
Decision Problems: Yes/no questions with multiple choices

Subsets Problem

// Generate all possible subsets
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> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        backtrack(nums, i + 1, current, result);
        current.remove(current.size() - 1); // Backtrack
    }
}

Permutations Problem

// Generate all possible permutations
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackPermute(nums, new ArrayList<>(), new boolean[nums.length], result);
    return result;
}

private void backtrackPermute(int[] nums, List<Integer> current, boolean[] used, 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]) {
            used[i] = true;
            current.add(nums[i]);
            backtrackPermute(nums, current, used, result);
            current.remove(current.size() - 1); // Backtrack
            used[i] = false;
        }
    }
}

N-Queens Problem

// Place n queens on n×n chessboard so no two queens attack each other
public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) {
        Arrays.fill(row, '.');
    }
    
    backtrackQueens(board, 0, result);
    return result;
}

private void backtrackQueens(char[][] board, int row, List<List<String>> result) {
    if (row == board.length) {
        result.add(constructSolution(board));
        return;
    }
    
    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrackQueens(board, row + 1, result);
            board[row][col] = '.'; // Backtrack
        }
    }
}

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

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

Common Backtracking Problems

Combinatorial: Subsets, permutations, combinations
Constraint Satisfaction: N-queens, sudoku solver
Path Finding: Maze solving, word search
Partitioning: Equal subset sum, palindrome partitioning
Graph Coloring: M-coloring problem

Open full interactive app