5.3.2 经典回溯算法问题
1. N皇后问题
2. 子集问题
问题描述：
给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。
生活例子：
想象你是一名餐厅经理，有一份包含多种食材的菜单（如牛肉、鸡肉、蔬菜、米饭）。顾客可以选择任意组合的食材来定制自己的餐点。你需要列出所有可能的组合选择，包括不选任何食材（空盘子）、只选一种食材、选两种食材的组合，一直到选择所有食材的组合。
问题分析：
对于一个长度为n的数组，其子集的数量为2^n个（包括空集）。这是因为对于每个元素，我们有两种选择：选或不选。
例如，对于数组[1,2,3]：
- 空集：[]
- 只包含一个元素的子集：[1], [2], [3]
- 包含两个元素的子集：[1,2], [1,3], [2,3]
- 包含三个元素的子集：[1,2,3]
回溯策略：
- 从空集开始，逐步考虑每个元素是否加入当前子集
- 对于每个元素，我们有两个选择：加入当前子集或不加入
- 每次做出选择后，递归处理剩余元素
- 当考虑完所有元素后，将当前子集加入结果集
图解过程（以[1,2,3]为例）：
[]
/ \
/ \
/ \
[1] []
/ \ / \
/ \ / \
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3][1,2][1,3][1][2,3][2][3][]
这个树形结构展示了回溯过程中的所有状态。每个节点表示一个子集，从根节点（空集）开始，每一层考虑一个元素是否加入。最终，所有叶子节点构成了所有可能的子集。
代码实现：
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// 从空集开始，逐步构建所有子集
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private static void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
// 将当前子集添加到结果中（每个状态都是一个有效的子集）
result.add(new ArrayList<>(current));
// 从start开始考虑每个元素，避免重复生成子集
for (int i = start; i < nums.length; i++) {
// 选择：将当前元素添加到子集中
current.add(nums[i]);
// 递归：处理剩余元素（只考虑当前元素之后的元素，避免重复）
backtrack(nums, i + 1, current, result);
// 回溯：将当前元素从子集中移除，尝试其他选择
current.remove(current.size() - 1);
}
}
// 打印所有子集（用于调试）
private static void printSubsets(List<List<Integer>> subsets) {
System.out.println("所有子集：");
for (List<Integer> subset : subsets) {
System.out.println(subset);
}
System.out.println("共 " + subsets.size() + " 个子集");
}
3. 全排列问题
问题描述：
给定一个不含重复数字的数组nums，返回其所有可能的全排列。
生活例子：
想象你是一名活动策划人，需要安排5位嘉宾的座次。每个座位只能坐一个人，每个人必须有座位。你需要列出所有可能的座位安排方式，以便选择最合适的一种。
问题分析：
对于长度为n的数组，其全排列的数量为n!（n的阶乘）。这是因为：
- 第一个位置有n种选择
- 第二个位置有n-1种选择
- 第三个位置有n-2种选择
- 以此类推
例如，对于数组[1,2,3]，其全排列有：
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]，共6=3!种。
回溯策略：
- 从空排列开始，逐步填入数字
- 对于每个位置，尝试填入尚未使用的每个数字
- 填入一个数字后，递归处理下一个位置
- 当所有位置都填满后，将当前排列加入结果集
- 回溯时，移除最后填入的数字，尝试其他可能
图解过程（以[1,2,3]为例）：
[]
/ | \
/ | \
/ | \
[1] [2] [3]
/ \ / \ / \
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
这个树形结构展示了回溯过程中的所有状态。从根节点（空排列）开始，每一层考虑一个位置应该填入哪个数字。最终，所有叶子节点构成了所有可能的全排列。
代码实现：
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new ArrayList<>(), result);
return result;
}
private static void backtrack(int[] nums, List<Integer> current, List<List<Integer>> result) {
// 如果当前排列的长度等于数组长度，说明找到了一个完整排列
if (current.size() == nums.length) {
// 将当前排列添加到结果中
result.add(new ArrayList<>(current));
return;
}
// 尝试在当前位置放置每个还未使用的数字
for (int i = 0; i < nums.length; i++) {
// 跳过已经使用的元素
if (current.contains(nums[i])) continue;
// 选择：将当前元素添加到排列中
current.add(nums[i]);
// 递归：处理下一个位置
backtrack(nums, current, result);
// 回溯：将当前元素从排列中移除，尝试其他选择
current.remove(current.size() - 1);
}
}
// 优化版本：使用布尔数组标记元素是否已使用，避免重复检查
public static List<List<Integer>> permuteOptimized(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrackOptimized(nums, new ArrayList<>(), used, result);
return result;
}
private static void backtrackOptimized(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++) {
// 使用布尔数组检查元素是否已使用，比contains()更高效
if (used[i]) continue;
current.add(nums[i]);
used[i] = true;
backtrackOptimized(nums, current, used, result);
current.remove(current.size() - 1);
used[i] = false;
}
}
// 打印所有排列（用于调试）
private static void printPermutations(List<List<Integer>> permutations) {
System.out.println("所有排列：");
for (List<Integer> perm : permutations) {
System.out.println(perm);
}
System.out.println("共 " + permutations.size() + " 个排列");
}