打卡第22天------回溯算法
开始学习了，希望我可以尽快成功上岸！
一、回溯理论基础
- 什么是回溯法？
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。
- 回溯法的效率
回溯法的本质是穷举，穷举所有可能，然后找出我们想要的答案。如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
组合无序，排列有序。
-
回溯法模板
回溯三部曲，可以按照如下步骤：
-
回溯函数模板返回值以及参数
-
回溯函数终止条件
-
回溯搜索的遍历过程
回溯函数遍历过程伪代码如下：
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果
}for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：
void backtracking(参数) {if (终止条件) {存放结果;return;}