回溯算法先容以及模板

回溯算法的理解：

• 回溯算法可以理解为一颗树形结构，即一颗n叉树，当遍历到叶子节点的时间，我们就到达了递归的终点，此时我们应该往上走。
  
• 回溯法解决的题目都可以抽象为树形结构，是的，我指的是所有回溯法的题目都可以抽象为树形结构！因为回溯法解决的都是在聚集中递归查找子集，聚集的大小就构成了树的宽度，递归的深度就构成了树的深度。
  

回溯法的服从

回溯法的性能如何呢，回溯并不是什么高效的算法，固然它很难理解，但是它的本质是枚举出所有环境。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操纵，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
因为没得选，一些题目能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
回溯算法的模板

• 回溯函数模板返回值以及参数
  

回溯算法中函数返回值一般为void。
再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时间那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
但后面的回溯题目标解说中，为了方便大家理解，我在一开始就帮大家把参数确定下来。
回溯函数伪代码如下：

1. void backtracking(参数)

复制代码

• 回溯函数终止条件
  

回溯要有中止条件
什么时间达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
所以回溯函数终止条件伪代码如下：

1. if (终止条件) {
2.     存放结果;
3.     return;
4. }

复制代码

• 回溯搜索的遍历过程
  

在上面我们提到了，回溯法一般是在聚集中递归搜索，聚集的大小构成了树的宽度，递归的深度构成的树的深度。
注意图中，我特意举例聚集大小和孩子的数量是相等的！
回溯函数遍历过程伪代码如下：

1. for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
2.     处理节点;
3.     backtracking(路径，选择列表); // 递归
4.     回溯，撤销处理结果
5. }

复制代码

for循环就是遍历聚集区间，可以理解一个节点有多少个孩子，这个for循环就实行多少次。
backtracking这里本身调用本身，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，如许就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个效果了。
分析完过程，回溯算法模板框架如下：
模板的代码：

1. void backtracking(参数) {
2.     if (终止条件) {
3.         存放结果;
4.         return;
5.     }
7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
8.         处理节点;
9.         backtracking(路径，选择列表); // 递归
10.         回溯，撤销处理结果
11.     }
12. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。