回溯法

import java.util.*;

public class BacktrackingExamples {

    // 1. 基础实现：子集问题
    public static List<List<Integer>> subsetsBasic(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrackBasic(nums, 0, new ArrayList<>(), result);
        return result;
    }
    
    private static void backtrackBasic(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        // 将当前路径添加到结果集
        result.add(new ArrayList<>(path));
        
        // 探索所有可能的选择
        for (int i = start; i < nums.length; i++) {
            // 做选择
            path.add(nums[i]);
            // 递归探索
            backtrackBasic(nums, i + 1, path, result);
            // 撤销选择（回溯）
            path.remove(path.size() - 1);
        }
    }
    
    // 2. 带剪枝的实现：组合总和（找出所有和为目标值的组合）
    public static List<List<Integer>> combinationSumWithPruning(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        // 排序以便剪枝
        Arrays.sort(candidates);
        backtrackWithPruning(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private static void backtrackWithPruning(int[] candidates, int target, int start, 
                                           List<Integer> path, List<List<Integer>> result) {
        // 找到符合条件的组合
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            // 剪枝：如果当前数字大于剩余目标值，后续数字更大，无需考虑
            if (candidates[i] > target) {
                break;
            }
            
            // 做选择
            path.add(candidates[i]);
            // 递归探索（允许重复使用同一元素，所以start仍为i）
            backtrackWithPruning(candidates, target - candidates[i], i, path, result);
            // 撤销选择（回溯）
            path.remove(path.size() - 1);
        }
    }
    
    // 3. N皇后问题优化实现
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        // 优化：使用数组记录皇后位置，col[i]表示第i行皇后所在的列
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        // 优化：使用集合记录已占用的列和对角线，加速判断
        Set<Integer> columns = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>(); // 行-列 为常数的对角线
        Set<Integer> diagonals2 = new HashSet<>(); // 行+列 为常数的对角线
        
        backtrackQueens(n, 0, queens, columns, diagonals1, diagonals2, result);
        return result;
    }
    
    private static void backtrackQueens(int n, int row, int[] queens, 
                                      Set<Integer> columns, Set<Integer> diagonals1, 
                                      Set<Integer> diagonals2, List<List<String>> result) {
        // 找到一个有效解
        if (row == n) {
            result.add(generateBoard(queens, n));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            int diagonal1 = row - col;
            int diagonal2 = row + col;
            
            // 剪枝：如果当前位置不合法（同列或同对角线已有皇后）
            if (columns.contains(col) || diagonals1.contains(diagonal1) || diagonals2.contains(diagonal2)) {
                continue;
            }
            
            // 做选择
            queens[row] = col;
            columns.add(col);
            diagonals1.add(diagonal1);
            diagonals2.add(diagonal2);
            
            // 递归探索下一行
            backtrackQueens(n, row + 1, queens, columns, diagonals1, diagonals2, result);
            
            // 撤销选择（回溯）
            queens[row] = -1;
            columns.remove(col);
            diagonals1.remove(diagonal1);
            diagonals2.remove(diagonal2);
        }
    }
    
    // 辅助方法：生成N皇后问题的棋盘表示
    private static List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
    
    // 测试
    public static void main(String[] args) {
        // 测试子集问题
        int[] nums = {1, 2, 3};
        System.out.println("子集问题结果:");
        List<List<Integer>> subsets = subsetsBasic(nums);
        for (List<Integer> subset : subsets) {
            System.out.println(subset);
        }
        
        // 测试组合总和问题
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        System.out.println("\n组合总和问题结果:");
        List<List<Integer>> combinations = combinationSumWithPruning(candidates, target);
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
        
        // 测试N皇后问题
        int n = 4;
        System.out.println("\n" + n + "皇后问题结果:");
        List<List<String>> queens = solveNQueens(n);
        for (List<String> board : queens) {
            for (String row : board) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}