什么是回溯算法？主要是在寻找和尝试的过程中找到解决问题的方法。当发现不满足求解条件时，就会“回溯”，返回尝试另一条路径。回溯法是一种最优搜索方法，根据最优条件向前搜索以达到目标。但是当探索到某一步时，如果原来的选择不是最优的或者达不到目标，那就退一步再做选择。称为“回溯点”。很多复杂、规模大的问题都可以使用回溯法，有“通用解题法”之誉。你明白吗，回溯算法其实是一个不断探索和试验的过程。探索成功，就成功了。有这样一个问题。找出加起来等于n的k个数字的所有组合。组合中只允许有1到9的正整数，每个组合中不能有重复的数字。解释：所有数字都是正整数。解决方案集不能包含重复的组合。示例1：输入：k=3,n=7输出：[[1,2,4]]示例2：输入：k=3,n=9输出：[[1,2,6],[1,3,5],[2,3,4]]这道题很明确，就是从1-9中选出k个数，它们的和等于n，这k个数不能重复。所以第一次选的时候可以选这9个数中的一个，顺着这个分支往下走，第二次选的时候可以选这9个数中的一个，但是因为不能重复，所以排除第一次选择，第二次选择时只能选择剩下的8个号码中的一个。。。这个选择过程比较清晰，我们可以把它看成一棵9点树，每个节点除叶子节点外还有9个子节点，即如下选择这9个数中的一个，即沿着任意一个继续走他的分支，其实就是DFS（不懂DFS的可以看373，数据结构-6，树），二叉树的DFS代码如下publicstaticvoidtreeDFS(TreeNoderoot){if(root==null)return;System.out.println(root.val);treeDFS(root.left);treeDFS(root.right);}这里可以像二叉树的DFS一样写一个9叉树，并且一棵9叉树的DFS通过递归遍历它的9个子节点，代码如下publicstaticvoidtreeDFS(TreeNoderoot){//递归必须有终止条件println(root.val);//通过循环，分别遍历9颗子树for(inti=1;i<=9;i++){//2，部分操作，可选，视情况而定treeDFS("i-th子节点");//3、一些操作，Optional，视情况而定}}DFS其实就相当于遍历他所有的分支，也就是列出他所有可能的结果，只要判断结果等于n就是我们要找的，那么这个9分树最多有多少层？因为有k个数，所以最多只能有k层。看代码publicList>combinationSum3(intk,intn){List>res=newArrayList<>();dfs(res,newArrayList<>(),k,1,n);returnres;}privatevoiddfs(List>res,Listlist,intk,intstart,intn){//终止条件，如果满足这个条件，再看没有意义if(list.size()==k||n<=0){//如果找到合适的集合，将其添加到集合列表中if(list.size()==k&&n==0)res.add(newArrayList<>(list));return;}//通过循环，分别遍历9颗子树for(inti=start;i<=9;i++){//选择当前值list.add(i);//递归dfs(res,list,k,i+1,n-i);//撤销选择list.remove(list.size()-1);}}代码比较简单，下面分析一下（看懂的可以直接跳过）.代码dfs中第一处就是终止条件的判断。426之前，什么是递归？通过本文，让你全面了解递归。在递归中提到，递归必须有一个终止条件。下面的for循环分别遍历了它的9个子节点。注意这里的i是从start开始的，所以可能没有9颗子树。前面说了，如果选了9个数中的一个，第二次只能从剩下的8个中选择，第三次只能从剩下的7个中选择...dsf第20行的开头是i+1，这就是为什么它是i+1。比如我选择了3，下次我就应该从4开始。如果我不加1，下次数字会从3开始重复，这显然不符合题中的要求。为什么for循环中的i不能每次都从1开始？一开始，如果每次都从1开始，结果会重复。例如，如果您选择[1,2]，那么下次您可能会选择[2,1]。如果不了解回溯算法，最后一行可能是最难理解的，为什么要撤销选择。经常看我公众号的同学可能知道，就是我常说的树枝污染问题，因为列表是引用传递的。当从一个分支跳转到另一个分支时，如果没有把上一个分支的数据给删除的话，链表会将上一个分支的数据带到下一个分支，从而导致错误的结果（下面会介绍）。那么除了去掉之前分支的数据之外，还有一种方式就是为每个分支创建一个列表，这样每个分支都是一个新的列表，互不干扰，也就是下图中的代码如下publicList>combinationSum3(intk,intn){List>res=newArrayList<>();dfs(res,newArrayList<>(),k,1,n);returnres;}privatevoiddfs(List>res,Listlist,intk,intstart,intn){//终止条件，如果满足这个条件，继续查找就没有意义了if(list.size()==k||n<=0){//如果找到合适的集合，将其添加到集合列表中if(list.size()==k&&n==0)res.add(newArrayList<>(list));return;}//通过循环，分别遍历9颗子树for(inti=start;i<=9;i++){//创建一个新的列表，并且原列表不会改变与当前列表的关系会影响之前的listListsubList=newLinkedList<>(list);subList.add(i);//递归dfs(res,subList,k,i+1,n-i);//注意这里没有取消操作,因为是在一个新的链表中修改，原来的链表没有被修改，//所以不需要undo操作}}我们看到最后没有undo操作，因为每一个分支都是一个newlist，你对当前分支的修改不会影响其他分支，所以不需要撤销操作。注意：尽量不要写这样的代码。这种方法虽然也能解决问题，但是每个分支都会重新创建列表，效率很低。要理解最后一行代码，首先要理解什么是递归。递归分为递归和递归两部分。递归就是往下传，递归就是往回走。你在哪里递归调用，你最终会回到哪里？我们画个简单的图看看，这是一棵非常简单的3叉树。如果要对其进行DFS遍历，当你沿着路径1→2路径往下走时，列表应该是[1,2]。因为是递归调用，所以最终还是会回到节点1，如果不去掉2，那么沿着1→4的分支走的时候就会变成[1,2,4]，但实际上是1→4这个的结果branch应该是[1,4]，因为我们从上一个分支中获取了值。遍历完1和2这两个节点后，最后回到节点1，回到节点1的时候要把节点2的值去??掉，这样链表就变成了[1]，然后沿着1→4这个分支往下走，结果为[1,4]。下面总结一下回溯算法的代码模板。privatevoidbacktrack("Originalparameter"){//终止条件（递归必须有终止条件）if("终止条件"){//一些逻辑操作（可选，视情况而定）return;}for(inti="for循环开始的参数";i<"for循环结束的参数";i++){//一些逻辑操作（可选，视情况而定）//取舍//递归回溯("newparameter");//一些逻辑操作（可选，视情况而定）//撤销选择}}有了模板，回溯算法的代码就很容易写了，下面写几个经典的答案根据模板回溯案例。八皇后问题八皇后问题也是一个非常经典的回溯算法问题。八皇后问题也有专门的介绍。不明白的可以先看看394，经典的八皇后问题和N皇后问题。他只是不断尝试，如果当前位置能放皇后，他就放，直到最后一行，如果他也能放，就意味着成功，如果某个位置放不下，回到上一步再试一次。比如我们先在第1行第1列放一个皇后，如下图，然后从第1列开始在第2行不冲突的位置放一个皇后，然后第3行……继续放就这样，如果能在第8行没有冲突就说明成功了。如果第8行之前有冲突，就回到上一步继续寻找合适的位置。。。看代码。//row表示在哪一行publicvoidsolve(char[][]chess,introw){//终止条件，row从0开始，最后一行可以放，表示成功if(row==chess.length){//自己写的一个public方法，打印二维数组，//Util.printTwoCharArrays(chess);System.out.println();return;}for(intcol=0;col>permute(int[]nums){List>list=newArrayList<>();backtrack(list,newArrayList<>(),nums);returnlist;}privatevoidbacktrack(List>list,ListtempList,int[]nums){//终止条件if(tempList.size()==nums.length){//寻找一组组合的说明list.add(newArrayList<>(tempList));return;}for(inti=0;i>subsets(int[]nums){List>list=newArrayList<>();//先排序Arrays.sort(nums);backtrack(list,newArrayList<>(),nums,0);returnlist;}privatevoidbacktrack(List>list,ListtempList,int[]nums,intstart){//注意这里不写终止条件。这不是说递归必须有终止条件吗？为什么这里不写呢？其实这里的终止条件//是隐含在for循环中的，当然我们也可以写成if(start>nums.length)rerurn;但此处省略。list.add(newArrayList<>(tempList));for(inti=start;i
