java如何穷举

穷举的基本概念

穷举是一种通过遍历所有可能的解来解决问题的方法。在Java中，穷举通常通过循环或递归实现，适用于解决组合、排列、子集等问题。

使用循环实现穷举

对于简单的问题，可以使用多重循环来穷举所有可能的组合。例如，找出所有三位数的水仙花数：

for (int i = 1; i <= 9; i++) {
    for (int j = 0; j <= 9; j++) {
        for (int k = 0; k <= 9; k++) {
            int num = i * 100 + j * 10 + k;
            if (i*i*i + j*j*j + k*k*k == num) {
                System.out.println(num);
            }
        }
    }
}

使用递归实现穷举

对于更复杂的问题，递归可以更灵活地实现穷举。例如，生成所有长度为n的二进制字符串：

void generateBinaryStrings(int n, String current) {
    if (n == 0) {
        System.out.println(current);
        return;
    }
    generateBinaryStrings(n - 1, current + "0");
    generateBinaryStrings(n - 1, current + "1");
}

回溯法优化穷举

回溯法是一种改进的穷举技术，通过剪枝避免不必要的计算。例如，解决八皇后问题：

void solveNQueens(int n, int row, int[] queens) {
    if (row == n) {
        printSolution(queens);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(queens, row, col)) {
            queens[row] = col;
            solveNQueens(n, row + 1, queens);
        }
    }
}

位运算加速穷举

对于状态空间较小的问题，可以使用位运算来提高穷举效率。例如，计算集合的所有子集：

void printSubsets(int[] nums) {
    int n = nums.length;
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                System.out.print(nums[i] + " ");
            }
        }
        System.out.println();
    }
}

动态规划与穷举结合

对于具有重叠子问题的问题，可以将动态规划与穷举结合。例如，计算斐波那契数列：

int fibonacci(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

注意事项

穷举法的时间复杂度通常较高，应谨慎用于大规模问题。在实际应用中，可以结合问题特点进行优化，如剪枝、记忆化或启发式搜索。