前言大家好，我是捡蜗牛的小男孩。我们在刷Leetcode的时候，经常会遇到回溯算法类型的题。回溯算法是五种基本算法之一，一般大厂都喜欢问。今天就和大家一起学习回溯算法的套路。如果文章中有不对的地方，欢迎大家指出。谢谢~什么是回溯算法？一道算法题进入回溯算法回溯算法框架例程Leetcode案例分析1.什么是回溯算法回溯算法，通过探索所有可能的候选解来找到所有解的算法。它使用试错的思想，它试图一步步解决一个问题。在一步步解题的过程中，当它发现已有的一步步答案无法得到有效正确的答案时，它会取消上一步甚至最后几步的计算，然后使用其他可能的点来解决问题。逐步解决方案尝试再次找到问题的答案。回溯法通常用最简单的递归方法来实现。反复重复上述步骤后，可能会出现两种情况：找到一个可能的正确答案；在尝试了所有可能的逐步方法后，声明该问题没有答案。举一个类似的生活例子，比如放羊童子在岔路口丢了羊。他沿着不同的岔路口寻找羊群，并试图在一个岔路口找到羊群。如果找不到羊，就一直往回走，在岔路口找另一条路，直到找到羊为止。下图是找羊的决策路线图：放羊童往A方向看，然后往C方向走，没找到就回到支路往D方向走。.untilhefindthesheep,这是回溯。2.在回溯算法中引入一个算法问题。给定一个没有重复数字的数组nums，返回它所有可能的排列。您可以按任何顺序返回答案。示例1：输入：nums=[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]例2：输入：nums=[0,1]输出：[[0,1],[1,0]]2.1实现思路看完这道题后，我们首先想到的是穷举所有的排列，但是没有规则你不会穷举吧？比如要排列3个数[1,2,3]，就先排列1，然后第二位只能是2或者3，如果第二位是2，那么第三位只能是3。。。我们可以借鉴羊的路线图找到羊，画出全排列的树图，如下：其实我们是不是从根节点开始遍历这棵树，记录路径的编号，然后走到叶子节点，就可以得到一个排列。遍历完所有的叶子节点，就可以得到完整的排列。如何更清楚地理解这棵树？为了方便理解，我们可以把nums中的k个数看做k个选择。例如，对于[1,2,3]，每个位有3个选择：1,2,3。每选择一个，就会展开一棵空间树。选择后，如果是重复的选择路径，则进行剪枝。上图中的树可以看做遍历所有元素，展开空间树，然后进行剪枝。如下图，知道了这棵树是怎么来的，我们来看看如何遍历找到完整的排列？每次我们走在树枝上，都像是在做决定。我们可以将行进路径和可用选项作为树节点的两个属性。如果你在根节点，你可以选择1、2或3，你走过的路径是空的。如下图所示，当你到达叶子节点时，你走过的路径数组的长度等于元素组的个数。这时，你走过的路就是满足条件的解。2.2代码实现代码怎么写？我们之前学树遍历，一般都是用递归，这道题也是用递归。什么是递归入口点？一条可选路径和一条已经走过的路径。递归函数体呢？枚举当前数组元素的for循环，需要if判断跳过剪枝递归退出？也就是说，它转到叶节点。叶子节点就是构造时已经构造好的路径。数组的长度等于nums的长度。实现代码如下：classSolution{//全数组，即所有路径集合List>allPath=newLinkedList<>();publicList>permute(int[]nums){//当前路径，入口路径，路径为空Listpath=newLinkedList<>();//递归函数入口，选择的是nums数组backTrace(nums,path);返回所有路径；}publicvoidbackTrace(int[]nums,Listpath){//走过的路径数组的长度等于nums的长度，也就是说已经到了叶子节点，所以它被添加到完整的数组集if(nums.length==path.size()){allPath.add(newLinkedList(path));返回;}for(inti=0;iallPath=[]voidbackTrace(optionallist,pathtraveled):if(endconditionsatisfied){allPath.add(pathtraveled);返回;}for(selection:optionallist){makeselectionbackTrace(currentoptionallist,pathtaken);undoselection}4.leetcode案例分析题目：给你一个没有重复元素的整数数组candidates和一个target整数target，找到candidates中可以显示的数字和target数字target的所有不同组合，并在a中返回列表形式。您可以按任何顺序调用这些组合。相同数量的候选人可以无限次重复选择。如果至少一个数字中的所选数字不同，则两个组合不同。示例1：输入：candidates=[2,3,6,7],target=7输出：[[2,2,3],[7]]解释：2和3可以组成一组候选项，2+2+3=7。注2可以多次使用。7也是候选者，7=7。只有这两种组合。示例2：输入：candidates=[2,3,5],target=8输出：[[2,2,2,2],[2,3,3],[3,5]]4.1我们需要先穷再找下一条规则，取例1的数据candidates=[2,3,6,7],target=7:7=2+2+37=7再取例2的数据:8=2+2+2+28=2+3+38=3+5其实规律比较明确。我们只需要将target中的candidates数组的元素逐一减去即可。如果能降为0，就是一个解。接下来，我们将绘制一棵树。我们可以把target作为树的根节点，然后分支代表candidates数组中间元素的减法，然后子节点就是target和数组元素的差值，如下：接下来，我们可以应用回溯算法，框架、走过的路径、可选列表、结束条件如何表示？看下图：如果走到橙色节点4的位置，optionallist是-2或者3，因为-6是负数La，怎么判断是optionallist呢？只要当前目标减去待选分支的值大于0，就可以作为可选列表。采取的路径是-3分支。结束条件呢？当你到达一个负数或0的节点时，就意味着该结束了，不能再做决定了。4.2代码实现最后我们设置下溯算法框架的伪代码如下：classSolution{List>allPath=newLinkedList<>();publicList>combinationSum(int[]candidates,inttarget){Listpath=newLinkedList<>();backTrace（候选人，目标，路径，0）；返回所有路径；}publicvoidbackTrace(int[]candidates,inttarget,Listpath,intstart){if(target<0){return;}//满足结束条件，加入总路径if(target==0){allPath.add(newArrayList(path));返回;}for(inti=start;i=candidates[i]){//做一个选择path.add(candidates[i]);//递归backTrace(candidates,target-candidates[i],path,i);//删除选择path.remove(path.size()-1);}}}}参考和感谢《labuladong的算法小抄》leetcode官网
