【递归、搜索与回溯算法】专题三——穷举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]]解题思路nnums.length。这题最先想到的就是搞n层循环每个循环固定一个数字但如果n100呢难道要手写100层循环吗本题要介绍全排列的一种很好的解法使用递归代替循环。也就是字面意思用递归代替每一层循环每层递归中进行枚举出某个数位上的数字当在一层递归中每固定一个数字就进行下一数位的枚举也就是进入下一层递归直到进行一次完整的全排列此时回溯回到上一层递归也就是少上一数位将这个数位的数换一个这个时候肯定要进行“恢复现场”继续重复往下一位枚举。全排列问题的枚举推导过程是可以画成上面这种“决策树”的所以就很适合使用递归算法了解题由“决策树”—递归算法这种思路要熟记下一题也是这样的。代码实现及解析classSolution{ListListIntegerret;ListIntegerpath;//记录每次更新的排列数相当于二叉树中的每个路径boolean[]used;//记录已经枚举过的数字publicListListIntegerpermute(int[]nums){retnewArrayList();pathnewArrayList();intnnums.length;usednewboolean[n];dfs(nums);returnret;}voiddfs(int[]nums){//递归出口if(path.size()nums.length){//path的每一位都确定了枚举的数字可以return了ret.add(newArrayList(path));//注意这里add的一定是path的副本return;}//path的位数还不够继续枚举下一位for(inti0;inums.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位置仍需要直接进入下一位数pos1的dfs而且dfs中的for循环是从形参pos开始的不然会导致子集重复。这样我们发现每次进入dfs其实都是一个结果所以方法二的效率是比方法一高的。决策图代码实现及解析方法一//解法一classSolution1{ListListIntegerret;ListIntegerpath;publicListListIntegersubsets(int[]nums){retnewArrayList();pathnewArrayList();dfs(nums,0);//从0下标开始遍历对每个位置进行选择returnret;}publicvoiddfs(int[]nums,intpos){//递归出口遍历到了最后也就是对每个位置都进行了“留与不留”的选择得到了一个完整子集if(posnums.length){ret.add(newArrayList(path));//再次强调要拷贝path的副本return;}//不选nums[pos]:dfs(nums,pos1);//选nums[pos]:path.add(nums[pos]);dfs(nums,pos1);//从上面这一句dfs出来后就要恢复现场path.remove(path.size()-1);}}方法二//解法二classSolution{ListListIntegerret;ListIntegerpath;publicListListIntegersubsets(int[]nums){retnewArrayList();pathnewArrayList();dfs(nums,0);returnret;}voiddfs(int[]nums,intpos){ret.add(newArrayList(path));//每次dfs都是一个结果if(posnums.length)return;//递归出口/*这层dfs表示要对该数位上的数字进行选择我们有多种选择所以用for循环 但是i一定要从pos位置开始不然就会导致子集重复pos代表前面遍历到的位置 */for(intipos;inums.length;i){path.add(nums[i]);//加上这一位数dfs(nums,i1);//直接选择下一位数path.remove(path.size()-1);//从上面这个dfs出来就要删除一位数进入下一个for循环重新选择}}}总结复习解题思路和代码注释来回忆代码实现框架决策树的概念、能推导出决策树的题目都可以这样使用递归算法来解题