回溯算法其实非常晦涩难懂。建议大家配合我的B站视频学习回溯算法。相信看完之后，你会解开对回溯算法的所有疑惑。什么是回溯法回溯法也可以称为回溯搜索法，是一种搜索方法。在二叉树系列中，我们不止一次提到回溯，比如二叉树：我以为用了递归，其实回溯是隐藏的。回溯是递归的副产品，只要有递归就会有回溯。所以在下面的解释中，回溯函数也是递归函数，指的是函数。回溯法的效率回溯法的性能如何？在这里我想跟大家说清楚。虽然回溯法比较难理解，但是回溯法并不是一个高效的算法。因为回溯的本质是穷举，穷举所有的可能性，然后选择我们想要的答案。如果想让回溯法更高效，可以增加一些剪枝操作，但不能改变回溯法的本质。那么既然回溯法效率不高，为什么还要用呢？因为没得选，有些问题如果能暴力搜一下就好了。如果你精疲力尽再剪枝，没有比这更高效的解决方案了。这时候大家应该很好奇了，这是什么问题，这么牛逼，只能暴力搜索了。回溯法解决的问题回溯法一般可以解决以下问题：组合问题：从N个数中按一定规则找出k个数的集合切割问题：一个字符串按一定规则有几种切割方法子集问题：有多少种N个数的集合中有符合条件的子集排列问题：N个数按一定规则完全排列，有几种排列。棋盘题：N皇后、解数独等，相信看完这些你就会发现，每道题都不简单！另外，有些同学可能分不清什么是组合，什么是排列？组合不强调元素的顺序，而排列强调元素的顺序。例如：{1,2}和{2,1}组合起来就是一个集合，因为不强调顺序，但是如果排列起来，{1,2}和{2,1}就是两个集合。记住组合无序，排列有序，就可以了。如何理解回溯法回溯法解决的问题可以抽象成树状结构。是的，我的意思是回溯法的所有问题都可以抽象成一个树结构！因为回溯法是解决在集合Set中递归寻找孩子的问题，集合的大小构成树的宽度，递归的深度，构成树的深度。递归必须有终止条件，所以一定是一棵有限高度的树（N-arytree）。这部分初学者可能看不懂。在后面回溯算法解决的所有问题中，我都会强调这一点，并画图给出相应的例子。现在只是有印象。回溯方法模板这里是Carl总结的回溯算法模板。在二叉树的递归中，我们讲到了递归三部曲，这里我给大家罗列一下回溯三部曲。回溯函数模板返回值和参数在回溯算法中，我的习惯是将函数命名为backtracking，大家可以随意命名。在回溯算法中，函数的返回值一般为void。再来看参数，因为回溯算法需要的参数不像二叉树递归的时候那么容易一次性确定，所以一般先写逻辑，然后需要什么参数随便填参数。但是在后面回溯题目的讲解中，为了方便大家的理解，一开始我会帮你确定参数。回溯函数的伪代码如下：voidbacktracking(parameter)由于回溯函数的终止条件是一个树结构，所以我们在讲解二叉树的递归时，就知道遍历必有一个终止条件树结构。所以回溯也有终止条件。当达到终止条件时，可以从树上看到。一般来说，当找到一个叶子节点时，找到一个满足条件的答案，并将答案存储起来，本级递归结束。所以回溯函数终止条件的伪代码如下：if(终止条件){storetheresult;return;}回溯搜索的遍历过程上面已经讲过了。回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，由递归的深度形成的树的深度。如图：回溯算法的理论基础注意图中，我特意举例说明集合的大小等于孩子的个数！回溯函数的遍历过程伪代码如下：size)){processingnode;backtracking(path,selectionlist);//递归回溯，撤销处理结果}for循环就是遍历集合区间。可以理解一个节点有多少个子节点，这个for循环执行了多少次。回溯在这里调用自己来实现递归。从图中可以看出for循环可以理解为水平遍历，回溯（递归）是垂直遍历，这样就遍历了整棵树。一般来说，搜索叶子节点是结果之一。分析流程后，回溯算法模板框架如下：voidbacktracking(参数){if(终止条件){存储结果；return;}for(selection:elementsinthislayercollection(树中子节点的个数为集合的大小)){Processingnode;backtracking(path,selectionlist);//递归回溯，撤消处理结果}}这个模板很重要，回溯题会用到！如果你从来没有学过回溯算法，看到这里会有些迷惑，不过后面开始讲解具体题目时会好一些。做过retrospectivemethodtopic的人看到这里应该会有同感。总结这篇文章，我们已经解释了什么是回溯算法，我们知道回溯和递归是相辅相成的。然后我提到了回溯法的效率。回溯法实际上是一种暴力搜索，不是一种高效的算法。然后列举了回溯法可以解决的几类问题。可见每一类问题都不简单。最后，我们提到回溯法解决的问题可以抽象成一个树结构（N-arytree），并给出了回溯法的模板。
