系统学习算法：专题九 穷举vs暴搜vs深搜vs回溯vs剪枝

其中标题的深搜，回溯，剪枝我们之前专题都已经有过学习和了解，这里多了两个穷举和暴搜，其实意思都差不多，穷举就是穷尽力气将所有情况都列举出来，暴搜就是暴力地去一个一个情况搜索，所以就是全部遍历的意思

而实现全部遍历之前，我们需要将所有情况以树状来大致画出来，这棵树就叫做决策树，也就是在上学时数学的某一小节学过的决策树，如下图

将123的所有排列情况列举出来

 就是填空一样，将不同情况画出树

那么这就涉及深搜，回溯和剪枝，只不过之前是二叉树，现在变为了多叉树

但过程都大致差不多，只要画出清晰的决策树，就可以将决策转化为代码

题目一：

 思路：

先画出决策树，就是上面我们举例的决策树

 其中我们需要一个全局变量二维数组ret来存储所有排列的情况，也是我们要返回的结果集

然后我们还需要一个全局变量一维数组path来记录其中一次的排列情况，也就做其中一条路径

然后还需要一个全局变量布尔数组来记录数字的使用情况，没使用过为false，使用过为true

然后我们就开始遍历，但注意我们是深搜dfs，不是宽搜bfs，即虽然画决策树的时候是先填第一个空1，2，3，但实际遍历我们是填1之后，将1对应的所有情况都搜索完之后，再回到2这里，即dfs的搜索顺序，而不是bfs

结束条件也很好想，就是当path的元素个数等于数组元素个数就说明排完了，那么就将该path填入结果集ret中（但注意path要重新new一个出来，不然传的是地址，后续搜索其他排列时，对path修改会连带着修改之前填入的path，即所有path都指向同一个path），填入之后还可以用剪枝稍微优化一下，因为填就说明全部元素用到了，后面的其他元素都没必要再搜索了，因为结果都是不可能的

而往下遍历的时候都是for循环数组的所有元素，调用布尔数组，如果该元素用过就不加，没用过就加，然后继续往下搜索

碰到结束条件后就该回溯，那么就该修改布尔数组和path，将该数的布尔值修改为false，再删除path的最后一个元素

最后返回ret即可

代码：

class Solution {//保存所有全排列的结果集List<List<Integer>> ret=new ArrayList<>();//用于判断该数字是否使用过boolean[] check;//其中一个排列List<Integer> path=new ArrayList<>();public void dfs(int[] nums){//如果排列元素的个数等于数组元素的个数，说明排完了if(path.size()==nums.length){//添加该排列情况（要new一个新的，不然就是传地址）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);}}}public List<List<Integer>> permute(int[] nums) { check=new boolean[nums.length];dfs(nums);return ret;}
}

题目二：

思路：

还是先画决策树，不同的决策树画法有不同的代码，但只要决策树画对，代码实现了就一定是对的

 求子集大概有两种决策树画法

解法1：

 这种决策树画法就是遍历数组，每遍历一个就出现两种决策，选或者不选，最后叶子结点就是所有的子集

代码1：

class Solution {//结果集List<List<Integer>> ret = new ArrayList<>();//其中一个子集List<Integer> path = new ArrayList<>();//k表示到数组的哪一个元素了public void dfs(int[] nums, int k) {//如果遍历完数组了if(k==nums.length){ret.add(new ArrayList<>(path));return;}//选path.add(nums[k]);dfs(nums,k+1);//恢复现场path.remove(path.size()-1);//不选dfs(nums,k+1);}public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return ret;}
}

解法2：

这种决策树的画法就是以子集中的元素个数来进行决策，一开始为0个，也就是空集，然后为1个，就是1，2，3，再然后为2个……其中是否选择以当前元素的位置为标准，比如1就找后面的2，3，而2就找后面的3，而3就没得找了，这样子就能避免出现重复的情况

则每一个结点都是一个结果，所以每次dfs的时候都要添加

代码2：

class Solution {//结果集List<List<Integer>> ret = new ArrayList<>();//其中一个子集List<Integer> path = new ArrayList<>();//k表示到数组的哪一个元素了public void dfs(int[] nums, int k) {//先添加ret.add(new ArrayList<Integer>(path));//从当前元素开始往后遍历for (int i = k; i < nums.length; i++) {//添加该元素path.add(nums[i]);//再次基础上往后遍历dfs(nums, i + 1);//恢复现场path.remove(path.size() - 1);}}public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return ret;}
}

但综合来看，肯定是解法2更优，因为每一个结点都是结果，没有多余的浪费，而解法1则全部枚举了出来，但最后只选择了叶子结点，非叶子结点就多余了

总结：

解决全排列，集合这种需要枚举许多情况并回溯的，先画出决策树，决策树不唯一，只要思路是对的，通过代码来实现，其中需要注意回溯后要恢复现场，最后就是正确的