回溯剪枝的 “减法艺术”：化解超时危机的 “救命稻草”(一)
专栏：算法的魔法世界
个人主页：手握风云
目录
一、例题讲解
1.1. 全排列
1.2. 子集
1.3. 找出所有子集的异或总和再求和
1.4. 全排列 II
一、例题讲解
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;}}
}