【递归、搜索与回溯算法】专题三——穷举vs暴搜vs深搜vs回溯vs剪枝

一、全排列

Leetcode链接
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解题思路

• n=nums.length。这题最先想到的就是搞n层循环，每个循环固定一个数字，但如果n==100呢？难道要手写100层循环吗？
• 本题要介绍全排列的一种很好的解法：使用递归代替循环。也就是字面意思，用递归代替每一层循环，每层递归中进行枚举出某个数位上的数字，当在一层递归中每固定一个数字就进行下一数位的枚举（也就是进入下一层递归），直到进行一次完整的全排列，此时回溯，回到上一层递归（也就是少上一数位）将这个数位的数换一个（这个时候肯定要进行“恢复现场”），继续重复往下一位枚举。

• 全排列问题的枚举推导过程是可以画成上面这种“决策树”的，所以就很适合使用递归算法了解题，由“决策树”—>递归算法，这种思路要熟记，下一题也是这样的。

代码实现及解析

classSolution{List<List<Integer>>ret;List<Integer>path;//记录每次更新的排列数（相当于二叉树中的每个路径）boolean[]used;//记录已经枚举过的数字publicList<List<Integer>>permute(int[]nums){ret=newArrayList<>();path=newArrayList<>();intn=nums.length;used=newboolean[n];dfs(nums);returnret;}voiddfs(int[]nums){//递归出口：if(path.size()==nums.length){//path的每一位都确定了枚举的数字，可以return了ret.add(newArrayList<>(path));//注意这里add的一定是path的副本return;}//path的位数还不够，继续枚举下一位for(inti=0;i<nums.length;i++){if(!used[i]){path.add(nums[i]);//添加上这一位数字used[i]=true;dfs(nums);//上面add已经固定了一位数字，继续尝试枚举下一位数字path.remove(path.size()-1);//这里是dfs回溯之后会执行到这里，要删除一位数，换一个数字add上（要进入下一层for循环，换个数进行固定）used[i]=false;//不要忘了删除这一位数后要将其的状态更改}}}}

总结

• 复习解题思路和代码实现及解析
• 可以看到在本题中，ret.add()操作添加的是path的副本，千万不可以将path直接添加进去，不然ret中储存的就都是同一个引用，path在后续还会不断进行更改，会造成严重的错误，这是多路径问题非常常见的一个易错点，不要不在乎。而且就算是没有像本题一样使用全局变量，而是进行了传参，但如果参数是引用类型，依然可能会存在上述所指出的问题，所以在多路径问题、使用全局变量这样的场景中必须重视这个问题

二、子集

Leetcode链接
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

解题思路

方法一：

• 对于【子集问题】我们可以对每个元素进行“留或不留”的决策，这是对于找子集问题的特点（包含不包含？不考虑排列）而推导出的方法。

遍历每个元素，对其进行选与不选的决定，画出决策图（“×1”代表不选1，“√1”代表选1）：

• 可以看到每次对数组所有元素都进行了决策之后就会得到一个结果

方法二：

• 第二种方法就是对于子集问题的结果我们可以发现其结果可以分类：不含有元素的（空集）、只包含1个元素的、包含两个元素的…
• 所以我们可以分组进行处理，0元素的、有一个元素的… ，但是代码实现不是想当然地写的，我们可以在dfs中用for循环对每个元素进行遍历，这样来做出不同的选择，但每固定一个数（pos位置）仍需要直接进入下一位数（pos+1）的dfs，而且dfs中的for循环是从形参pos开始的，不然会导致子集重复。这样我们发现每次进入dfs其实都是一个结果，所以方法二的效率是比方法一高的。

决策图：

代码实现及解析

方法一：

//解法一：classSolution1{List<List<Integer>>ret;List<Integer>path;publicList<List<Integer>>subsets(int[]nums){ret=newArrayList<>();path=newArrayList<>();dfs(nums,0);//从0下标开始遍历，对每个位置进行选择returnret;}publicvoiddfs(int[]nums,intpos){//递归出口：遍历到了最后，也就是对每个位置都进行了“留与不留”的选择，得到了一个完整子集if(pos==nums.length){ret.add(newArrayList<>(path));//再次强调要拷贝path的副本return;}//不选nums[pos]:dfs(nums,pos+1);//选nums[pos]:path.add(nums[pos]);dfs(nums,pos+1);//从上面这一句dfs出来后就要恢复现场：path.remove(path.size()-1);}}

方法二：

//解法二：classSolution{List<List<Integer>>ret;List<Integer>path;publicList<List<Integer>>subsets(int[]nums){ret=newArrayList<>();path=newArrayList<>();dfs(nums,0);returnret;}voiddfs(int[]nums,intpos){ret.add(newArrayList<>(path));//每次dfs都是一个结果if(pos==nums.length)return;//递归出口/*这层dfs表示要对该数位上的数字进行选择，我们有多种选择，所以用for循环， 但是i一定要从pos位置开始，不然就会导致子集重复（pos代表前面遍历到的位置） */for(inti=pos;i<nums.length;i++){path.add(nums[i]);//加上这一位数dfs(nums,i+1);//直接选择下一位数path.remove(path.size()-1);//从上面这个dfs出来，就要删除一位数，进入下一个for循环重新选择}}}

总结

• 复习解题思路和代码注释来回忆代码实现框架
• 决策树的概念、能推导出决策树的题目都可以这样使用递归算法来解题