专栏：算法的魔法世界
个人主页：手握风云
目录
一、例题讲解
1.1. 全排列
找出数组的全排列。
我们先来考虑穷举，利用多层for循环枚举出所有结果放入数组中。明显这种算法时间复杂度很大。我们先画出决策树(越详细越好)，如果我们在遍历的过程中碰到相同的数字，就可以进行剪枝操作。因为在每个节点干的事情是相同的，就可以采用递归的代码。
我们先来定义全局变量：List<List<Integer>> ret作为最后返回值，存储所有的结果序列。List<Integer> path用来记录在深搜过程中遍历过的节点，如果当前节点的数据符合要求，就添加进path里面。如果path的长度等于nums的长度，就可以进行回溯，把最后一个元素删除。接下来我们重点考虑如何剪枝，也就是判断当前路径上的数不能重复使用。我们再定义一个布尔类型的数组用于标记元素是否被使用过，如果使用过，就把里面对应的nums下标的位置的元素设置为true。
最后就是设计递归方法，枚举nums里的元素，如果没有使用过，就可以添加进path中。当如果进行回溯时，不光要删除path的最后一个元素，还要将当前下标的布尔值设为false。递归的出口，当遍历到叶子节点时，直接添加进path中。
完整代码实现：
class Solution {
List<List<Integer>> ret;
List<Integer> path;
boolean[] check;
public List<List<Integer>> permute(int[] nums) {
ret = new ArrayList<>();
path = new ArrayList<>();
check = new boolean[nums.length];
dfs(nums);
return ret;
}
private void dfs(int[] nums) {
if (nums.length == path.size()) {
ret.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (check[i] == false) {
path.add(nums[i]);
check[i] = true;
dfs(nums);
check[i] = false;
path.remove(path.size() - 1);
}
}
}
}1.2. 子集
找到不包含重复元素数组的全部子集。
我们依然是先画出决策树：
解法一：根据上面的决策树，我们很明显需要对这棵完全二叉树进行深度优先搜索。首先定义一个全局变量List<Integer> path用于储存正在构建的子集，如果都不选，那么就返回一个空的数组，还需要一个全局变量List<List<Integer>>作为返回值用于存储最终生成的所有子集。当我们进行深搜的时候，我们需要将数组的下一个元素添加进去，所以递归方法不光需要nums一个参数，还需要nums的下标i。当我们遍历数组某个位置i时，如果选择该元素，就把该元素添加进path中，如果不选，直接递归执行下一个位置。注意：回溯上一个位置之前，如果选择了该元素，需要删除该元素以恢复现场。递归出口就是遍历到叶子节点。
解法二：我们还是以示例1nums={1,2,3}为例，子集既可以是空集、含1个元素、2个元素或者3个元素，就可以画出如下图的决策树，这样每个节点就都是我们想要的结果。每当选完一个数之后，就只能选择后面的位置。回溯与解法一相同。
完整代码实现：
// 解法一
class Solution {
//用于存储所有子集
List<List<Integer>> ret;
// 存储当前正在构建的子集
List<Integer> path;
public List<List<Integer>> subsets(int[] nums) {
ret = new ArrayList<>();
path = new ArrayList<>();
// 从第一个元素开始深度优先搜索
dfs(nums, 0);
return ret;
}
public void dfs(int[] nums, int pos) {
if (pos == nums.length) {
ret.add(new ArrayList<>(path));
return;
}
// 选择当前数字
path.add(nums[pos]);
dfs(nums, pos + 1);
// 回溯，不选择当前数字
path.remove(path.size() - 1);
dfs(nums, pos + 1);
}
}// 解法二
class Solution {
//用于存储所有子集
List<List<Integer>> ret;
// 存储当前正在构建的子集
List<Integer> path;
public List<List<Integer>> subsets(int[] nums) {
ret = new ArrayList<>();
path = new ArrayList<>();
// 从第一个元素开始深度优先搜索
dfs(nums, 0);
return ret;
}
public void dfs(int[] nums, int pos) {
ret.add(new ArrayList<>());
for (int i = pos; i < nums.length; i++) {
path.add(nums[i]);
dfs(nums[i], i + 1);
ret.remove(path.size() - 1);
}
}
}1.3. 找出所有子集的异或总和再求和
本题要求计算给定数组nums中所有子集的异或总和，并返回这些异或总和的总和。
本题需要先求子集，可以仿照上一题解法二的思路。我们先定义全局变量sum用于累加所有子集的异或和，还有path用于在深度优先搜索过程中记录当前路径的异或值。递归方法不光要传数组，还需要传入数组的小标。回溯时需要注意，恢复现场只需异或同样的数字即可。
完整代码实现：
class Solution {
int path;
int sum;
public int subsetXORSum(int[] nums) {
dfs(nums, 0);
return sum;
}
// 深度优先搜索，用于计算所有可能的异或路径和
private void dfs(int[] nums, int pos) {
sum += path;
for (int i = pos; i < nums.length; i++) {
path ^= nums[i];
dfs(nums, i + 1);
// 回溯，恢复路径值到之前的状态
path ^= nums[i];
}
}
}1.4. 全排列 II
给定一个可能包含重复数字的序列nums，返回该序列所有不重复的全排列。
这道题与《全排列》不同的是，需要剪更多的枝。我们以示例1为例，当第一个位置选了第一个1，那么剩下的就需要从“1,2”中选；当第一个位置选第二个1，那么剩下的也是从“1,2”中选。并且使用过的数字不能再次选择。所以剪枝策略为同一个节点的所有分支中，相同的元素只能选择一次；同一个数只能使用一次，我们还是需要布尔类型的数组作为全局变量来判断来。
如果 check[i] 为 true，表示该元素已经在当前排列/组合中被使用，需要跳过。当数组中有重复元素时（如 [1, 1, 2]），如果不加处理，可能会生成重复的排列/组合。这里的逻辑是：如果当前元素与前一个元素相同，且前一个元素未被使用（!check[i - 1]），则跳过当前元素。
完整代码实现：
public class Solution {
List<Integer> path;
List<List<Integer>> ret;
boolean[] check;
public List<List<Integer>> permuteUnique(int[] nums) {
path = new ArrayList<>();
ret = new ArrayList<>();
check = new boolean[nums.length];
Arrays.sort(nums);
// 深度优先搜索生成全排列
dfs(nums, 0);
return ret;
}
private void dfs(int[] nums, int pos) {
// 递归出口
if (pos == nums.length) {
ret.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 跳过已使用的数字
if (check[i] || (i != 0 && nums[i] == nums[i - 1] && !check[i - 1])) {
continue;
}
path.add(nums[i]);
check[i] = true;
dfs(nums, pos + 1);
path.remove(path.size() - 1);
check[i] = false;
}
}
}