如果人生可以让你重新选择，以消耗十年寿命的代价，你会想回到哪一年？
这个问题，我，没有答案。
因为这个问题，没有答案。
2004年有一部电影《蝴蝶效应》——讲的就是主人公为了达到自己的目标，一直通过回溯的方法，回到童年，在关键的岔路口，重新做选择。
这个回溯一切的想法是虚幻的，不存在的。我们只能憧憬，不能实现。
但是回溯的算法是存在的。
是的，今天我们要来学习四大经典算法中的回溯算法——
一、回溯算法的应用场景
1.1 应用于哪类场景？
首先。我们想问，
- 回溯算法的应用情景都有哪些？
它可以指导深度优先搜索这种经典的算法设计，also可以用在很多实际的软件开发场景中，比如正则表达式匹配、编译原理中的语法分析等。
除此之外，很多经典的数学问题都可以用回溯算法解决，比如数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列等等。
1.2 应用于哪类问题？
In general，回溯算法always都应用在“搜索”这类问题上。
不过这并不是狭义的指我们前面讲过的图的搜索算法，而是在一组可能的解中，搜索满足期望的解。
回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。
为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段——每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
1.3 属于你的八皇后
假设There有一个8×8的棋盘，我们hope往里面放8个棋子，这里的棋子就是皇后，原则是每个皇后所在的行，列，对角线都不能有另一个棋子。
- 既然是8个皇后，就将问题分为8个阶段。
依次将 8 个棋子放到第一行、第二行、第三行……第八行。
在放置的过程中，need不停地检查当前放法，是否满足要求。
- 如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。
二、回溯算法的实现
2.1 回溯算法怎么实现？
回溯算法的实现是依靠递归代码来实现的。
2.2 回溯算法的经典应用1——0-1背包
- Q：有一个背包，背包总的承载重量是 Wkg。现在有 n 个物品，每个物品的重量不等，并且不可分割。现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
这个问题和贪心算法的区别是：贪心问题中，物品是可以分割的，也就是说，可以将某个物品的一部分装到背包里。
而回溯算法的这个0-1背包问题，物品是不可分割的，要么都装上，要么就不装。
那么，回溯算法是如何做的呢？
- 把物品依次排列，整个问题就分解为了n个阶段。
- 分成n个阶段后，each阶段对应each物品怎么选择。
- 先对first物品进行处理，选择装进去或者不装。
- 再递归地处理剩下rest的物品。
当然，这里还用到了一点搜索剪枝的技巧，
- 这个技巧是什么呢？
当发现已经选择的物品的重量超过了Wkg后，停止继续探测剩下的物品。
2.3 回溯算法的经典应用2——正则表达式匹配
In actually, 正则表达式中最重要的一种算法思想就是回溯。
- 正则表达式中，最重要的就是通配符，
假设正则表达式中只包含“&”和“?”这两种通配符，并且对这两个通配符的语义稍微做些改变——
其中，“&”匹配任意多个（大于等于 0 个）任意字符，“?”匹配零个或者一个任意字符。
基于以上背景假设，我们看下，如何用回溯算法，判断一个给定的文本，能否跟给定的正则表达式匹配？
We依次考察正则表达式中的每个字符，
当是非通配符时，我们就直接跟文本的字符进行匹配，
如果相同，则继续往下处理；如果不同，则回溯。
如果遇到特殊字符的时候，我们就有多种处理方式了，也就是所谓的岔路口，比如“&”有多种匹配方案，可以匹配任意个文本串中的字符，我们就先随意的选择一种匹配方案，然后继续考察剩下的字符。
如果中途发现无法继续匹配下去了，我们就回到这个岔路口，重新选择一种匹配方案，然后再继续匹配剩下的字符。
三、自问自答环节
- 大部分情况下，回溯算法都用来解决什么问题？具体的问题有哪些？
大部分情况下，都是用来解决广义的搜索问题，i.e.，从一组可能的解中，选择出一个满足要求的解。
可以解决的问题非常多，比如开头提到的深度优先搜索、八皇后、0-1 背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配等等。
- 回溯算法用什么方法实现比较好？
回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。
利用剪枝，We并不需要穷举搜索所有的情况，从而improve搜索效率。
回溯算法本质上就是枚举，优点在于其类似于摸着石头过河的查找策略，且可以通过剪枝少走冤枉路。
它可能适合应用于缺乏规律，或我们还不了解其规律的搜索场景中。
回溯就是暴力枚举的解法，遍历所有情况，当满足情况就停止遍历（剪枝）。
