Backtracking Cheat Sheet in Java (From Basics to Advanced)

961

Backtracking Cheat Sheet in Java (From Basics to Advanced)

Backtracking is a general algorithmic technique used to solve optimization problems. It explores all possible options by exploring each path one by one, and when it encounters an invalid solution or dead end, it "backtracks" to try another path.

Basic Structure of Backtracking

The general backtracking template can be broken down into these steps:

Choice: Make a decision or pick an option.
Constraints: Ensure that the decision meets the required constraints.
Goal: Check if we have reached the goal (solution).
Backtrack: If a solution is not possible, undo the last decision and try the next option.

General Steps:

public class Backtracking {

    public void backtrack(int start, List<Integer> path) {
        // Base case: if the path meets the goal, return the solution
        if (path.size() == targetLength) {
            // Process the path
            return;
        }

        // Try all possible choices
        for (int i = start; i < options.length; i++) {
            // Make the choice
            path.add(options[i]);

            // Recurse with the updated path
            backtrack(i + 1, path);

            // Backtrack: undo the choice
            path.remove(path.size() - 1);
        }
    }
}

Basic Backtracking Examples

1. Permutations (Unique Elements)

Problem: Generate all possible permutations of a string or array.

import java.util.*;

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

    private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums) {
        if (temp.size() == nums.length) {
            result.add(new ArrayList<>(temp));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (temp.contains(nums[i])) continue; // Skip duplicates
            temp.add(nums[i]);
            backtrack(result, temp, nums);
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        Permutations sol = new Permutations();
        int[] nums = {1, 2, 3};
        System.out.println(sol.permute(nums)); // [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    }
}

2. Subsets (All Possible Subsets)

Problem: Generate all possible subsets of a given set.

import java.util.*;

public class 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> temp, int[] nums, int start) {
        result.add(new ArrayList<>(temp));
        for (int i = start; i < nums.length; i++) {
            temp.add(nums[i]);
            backtrack(result, temp, nums, i + 1); // Move to the next index
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        Subsets sol = new Subsets();
        int[] nums = {1, 2, 3};
        System.out.println(sol.subsets(nums)); // [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    }
}

Advanced Backtracking Examples

3. N-Queens Problem

Problem: Place N queens on an N x N chessboard such that no two queens threaten each other.

import java.util.*;

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[] columns = new boolean[n]; // Tracks used columns
        boolean[] diag1 = new boolean[2 * n - 1]; // Tracks major diagonals
        boolean[] diag2 = new boolean[2 * n - 1]; // Tracks minor diagonals
        backtrack(result, new ArrayList<>(), n, 0, columns, diag1, diag2);
        return result;
    }

    private void backtrack(List<List<String>> result, List<String> temp, int n, int row,
                           boolean[] columns, boolean[] diag1, boolean[] diag2) {
        if (row == n) {
            result.add(new ArrayList<>(temp));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (columns[col] || diag1[row - col + n - 1] || diag2[row + col]) continue;
            char[] boardRow = new char[n];
            Arrays.fill(boardRow, '.');
            boardRow[col] = 'Q';
            temp.add(new String(boardRow));

            columns[col] = true;
            diag1[row - col + n - 1] = true;
            diag2[row + col] = true;

            backtrack(result, temp, n, row + 1, columns, diag1, diag2);

            temp.remove(temp.size() - 1); // Backtrack
            columns[col] = false;
            diag1[row - col + n - 1] = false;
            diag2[row + col] = false;
        }
    }

    public static void main(String[] args) {
        NQueens sol = new NQueens();
        System.out.println(sol.solveNQueens(4)); 
    }
}

4. Sudoku Solver

Problem: Solve a Sudoku puzzle.

public class SudokuSolver {
    public void solveSudoku(char[][] board) {
        backtrack(board);
    }

    private boolean backtrack(char[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;
                            if (backtrack(board)) {
                                return true;
                            }
                            board[row][col] = '.'; // Backtrack
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num ||
                board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'', '3', '.', '.', '4', '1', '.', '.', '9'}
        };
        SudokuSolver solver = new SudokuSolver();
        solver.solveSudoku(board);
    }
}

Tips for Backtracking:

Pruning:
- Try to cut off invalid branches early by adding constraint checks in your algorithm. This improves performance.
State Space Exploration:
- Always consider the problem as a tree where each node is a state, and each branch represents a possible decision.
Memoization:
- In some cases, backtracking can be optimized using memoization (storing results of subproblems) to avoid redundant calculations.
Iteration vs Recursion:
- While backtracking is typically implemented recursively, it can also be done iteratively using an explicit stack.

Time Complexity:

Backtracking typically involves exploring every possibility. Hence, its time complexity is often exponential in the size of the input, such as (O(2^n)) or (O(n!)) depending on the problem's structure. However, pruning and constraints can significantly reduce the number of recursive calls, making it feasible in many cases.

Conclusion:

Backtracking is a versatile algorithm used to solve a variety of problems like permutations, combinations, Sudoku, N-Queens, etc. The key to optimizing backtracking is pruning the search space effectively.

Comments (1)