穷举vs暴搜vs深搜vs回溯vs剪枝

穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝 1. 全排列2. 子集

1. 全排列

题目链接：46. 全排列

算法原理：

画出决策树

设计函数

全局变量：二维数组ret存储结果；一维数组path存储路径；boolean类型一维数组visited表示当前节点是否已经被使用深度优先遍历dfs，当某个节点被使用后，标记为true剪枝：当某个节点已经被使用过时，该分支剪掉回溯：visited[i] 回溯为 false，path的最后一个元素删除递归的出口：当path的大小和nums的大小相等时，将path存入ret中，并返回

实现代码：

class Solution { public List<List<Integer>> ret; public List<Integer> path; boolean[] visited; public List<List<Integer>> permute(int[] nums) { ret = new ArrayList<>(); path = new ArrayList<>(); visited = new boolean[nums.length]; dfs(nums); return ret; } private void dfs(int[] nums) { if(path.size() == nums.length) { //将路径添加进结果中 ret.add(new ArrayList<>(path)); return; } for(int i = 0; i < nums.length; i++) { //当当前节点未使用时 if(!visited[i]) { path.add(nums[i]);//添加当前节点到路径中 visited[i] = true;//标记当前节点已经使用 dfs(nums); //回溯 visited[i] = false; path.remove(path.size() - 1); } } } } 2. 子集

题目链接：78. 子集

算法流程： 解法一：

画出决策树：以数组[1, 2, 3]为例，对每个元素分为选与不选两种操作 由此可知，决策树的叶子节点就是该数组的子集

设计代码

全局变量：一维数组path存储所经过的路径，二维数组ret存储所得的结果dfs：函数头dfs(int[] nums, int i)，分为选择nums[i]和不选择nums[i]，选择nums[i]所需进行的操作为path尾部加入nums[i]。并dfs(nums, i+1)；不选择nums[i]所需进行的操作为dfs(nums, i+1)细节问题：剪枝，回溯，递归出口。这道题不需要剪枝；回溯操作为删除path尾部的元素；递归出口为i == nums.length，将该路径存到ret中，返回

实现代码：

class Solution { public List<Integer> path; public List<List<Integer>> ret; public List<List<Integer>> subsets(int[] nums) { path = new ArrayList<>(); ret = new ArrayList<>(); dfs(nums, 0); return ret; } private void dfs(int[] nums, int i) { if(i == nums.length) { ret.add(new ArrayList<>(path)); return; } dfs(nums, i+1); path.add(nums[i]); dfs(nums, i+1); path.remove(path.size()-1); } }

解法二： 算法流程：

画出决策树：以数组[1, 2, 3]为例，分为选择0，1，2，3个元素 在进行下一步选择元素时，只能去选择上一步所选元素后面的元素

设计代码

全局变量：一维数组path存储所经过的路径，二维数组ret存储所得的结果dfs：函数头dfs(int[] nums, int pos)，pos代表上一步所选元素后面一个元素的下标细节问题：回溯，即删除path尾部的元素

实现代码：

class Solution { public List<Integer> path; public List<List<Integer>> ret; public List<List<Integer>> subsets(int[] nums) { path = new ArrayList<>(); ret = new ArrayList<>(); dfs(nums, 0); return ret; } private void dfs(int[] nums, int pos) { ret.add(new ArrayList<>(path)); for(int i = pos; i < nums.length; i++) { path.add(nums[i]); dfs(nums, i+1); path.remove(path.size()-1); } } }