打卡第22天------回溯算法

开始学习了，希望我可以尽快成功上岸！

一、回溯理论基础

• 什么是回溯法？

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

• 回溯法的效率

回溯法的本质是穷举，穷举所有可能，然后找出我们想要的答案。如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

组合无序，排列有序。

• 回溯法模板

回溯三部曲，可以按照如下步骤：

1. 回溯函数模板返回值以及参数

2. 回溯函数终止条件

3. 回溯搜索的遍历过程 

回溯函数遍历过程伪代码如下：

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

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

分析完过程，回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }