Backtracking Fundamentals

class BacktrackDemo {
    static void recursiveDemo(int step, LinkedList<String> path) {
        if (step == 3) return;
        
        System.out.println("Entering: " + path);
        path.add("step");
        recursiveDemo(step + 1, path);
        path.removeLast();
        System.out.println("Exiting: " + path);
    }
}

Permutations (Leetcode 46)

class Permutations {
    static List<List<Integer>> generatePermutations(int[] elements) {
        List<List<Integer>> results = new ArrayList<>();
        backtrack(elements, new boolean[elements.length], 
                 new LinkedList<>(), results);
        return results;
    }

    static void backtrack(int[] nums, boolean[] used, 
                         LinkedList<Integer> current, 
                         List<List<Integer>> output) {
        if (current.size() == nums.length) {
            output.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            
            current.add(nums[i]);
            used[i] = true;
            backtrack(nums, used, current, output);
            used[i] = false;
            current.removeLast();
        }
    }
}

Unique Permutations (Leetcode 47)

class UniquePermutations {
    static List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        permute(nums, new boolean[nums.length], 
               new LinkedList<>(), result);
        return result;
    }

    static void permute(int[] nums, boolean[] visited, 
                       LinkedList<Integer> path, 
                       List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i-1] && !visited[i-1])) 
                continue;
                
            path.add(nums[i]);
            visited[i] = true;
            permute(nums, visited, path, result);
            visited[i] = false;
            path.removeLast();
        }
    }
}

Cmobinations (Leetcode 77)

class Combinations {
    static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        generateCombinations(1, n, k, new LinkedList<>(), result);
        return result;
    }

    static void generateCombinations(int start, int n, int remaining, 
                                    LinkedList<Integer> combo, 
                                    List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(combo));
            return;
        }
        
        for (int i = start; i <= n; i++) {
            if (remaining > n - i + 1) continue;
            
            combo.add(i);
            generateCombinations(i + 1, n, remaining - 1, combo, result);
            combo.removeLast();
        }
    }
}

Combination Sum (Leetcode 39)

class CombinationSum {
    static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        findCombinations(candidates, target, 0, 
                        new LinkedList<>(), result);
        return result;
    }

    static void findCombinations(int[] nums, int remaining, int start, 
                               LinkedList<Integer> current, 
                               List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > remaining) continue;
            
            current.add(nums[i]);
            findCombinations(nums, remaining - nums[i], i, current, result);
            current.removeLast();
        }
    }
}

N-Queens Problem (Leetcode 51)

class NQueens {
    static List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        
        solve(0, board, new boolean[n], 
              new boolean[2*n-1], new boolean[2*n-1], 
              solutions);
        return solutions;
    }

    static void solve(int row, char[][] board, boolean[] cols, 
                     boolean[] diag1, boolean[] diag2, 
                     List<List<String>> result) {
        if (row == board.length) {
            result.add(createSolution(board));
            return;
        }
        
        for (int col = 0; col < board.length; col++) {
            int d1 = row + col;
            int d2 = row - col + board.length - 1;
            
            if (cols[col] || diag1[d1] || diag2[d2]) continue;
            
            board[row][col] = 'Q';
            cols[col] = diag1[d1] = diag2[d2] = true;
            solve(row + 1, board, cols, diag1, diag2, result);
            cols[col] = diag1[d1] = diag2[d2] = false;
            board[row][col] = '.';
        }
    }
    
    static List<String> createSolution(char[][] board) {
        List<String> solution = new ArrayList<>();
        for (char[] row : board) solution.add(new String(row));
        return solution;
    }
}

Sudoku Solver (Letecode 37)

class SudokuSolver {
    static void solveSudoku(char[][] board) {
        solve(board, 0, 0);
    }

    static boolean solve(char[][] board, int row, int col) {
        if (row == 9) return true;
        if (col == 9) return solve(board, row + 1, 0);
        if (board[row][col] != '.') return solve(board, row, col + 1);
        
        for (char num = '1'; num <= '9'; num++) {
            if (isValid(board, row, col, num)) {
                board[row][col] = num;
                if (solve(board, row, col + 1)) return true;
                board[row][col] = '.';
            }
        }
        return false;
    }
    
    static boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num) return false;
            if (board[i][col] == num) return false;
            int boxRow = 3 * (row / 3) + i / 3;
            int boxCol = 3 * (col / 3) + i % 3;
            if (board[boxRow][boxCol] == num) return false;
        }
        return true;
    }
}