在一般的递归函数中，如二分查找、反转文件等，在每个决策点只需要调用一个递归（比如在二分查找，在每个节点我们只需要选择递归左子树或者右子树），在这样的递归调用中，递归调用形成了一个线性结构，而算法的性能取决于调用函数的栈深度。比如对于反转文件，调用栈的深度等于文件的大小；再比如二分查找，递归深度为O(nlogn)，这两类递归调用都非常高效。

?

现在考虑子集问题或者全排列问题，在每一个决策点我们不在只是选择一个分支进行递归调用，而是要尝试所有的分支进行递归调用。在每一个决策点有多种选择，而这多种选择的每一个选择又导致了更多的选择，直到我们碰到base case。这样的话，随着递归调用的深入，穷举递归(exhaustive recursion)算法时间复杂度就会很高。比如：在每个决策点我们需要确定选择哪个一个字母或者在当前位置选择下一步去哪个城市（TSP）。那么我们有办法避免代价高昂的穷举递归吗？答案是视情况而定。在有些情况下，我们没有办法，必须穷举递归，比如我们需要找到全局的最优解。然而在更多的情况下我们只希望找到满意解，在每个决策点，我们选择只选择一条递归调用路径，希望它能够成功，如果我们最终发现，可以得到一个满意解，OK我们不再遍历其他的情况了。否则如果这次尝试没有成功，我们退回决策点，换一个选择尝试，这就是回溯算法。值得说明的是，关于回溯的深度，我们只需要向上回溯到最近的决策点，该决策点满足还有其他的选择没有尝试。随着回溯的向上攀升，最终我们可能回到初始状态，这时候其实我们已经穷举递归了所有的情况，那么该问题是不可解的。

?

典型问题回顾

上面说的是不是很抽象？我也觉得，但是没办法，严谨还是要有的，说的再多不如来看几个例子来得实在，毕竟我们学习它是为了解决实际问题的。

?

【经典穷举问题】穷举所有的排列

问题描述：给定一个字符串，重排列后输出所有可能的排列。

?

在每个决策点，我们需要在剩余待处理的字符串中，选择一个字母，假设剩余字符串长度为k，那么在每个决策点我们有k种选择，我们对每个选择都尝试一次，每次选择一个后，更新当前已经字符串和剩余字符串。当剩余字符串为空时，我们到达base case，输出当前选择的字符串即可。伪代码及C++代码如下：

?

复制代码

?1 // Permutation Problem

?2 // If you have no more characters left to rearrage, print the current permutation

?3 // for (every possible choice among the characters left to rearrage)

?4 // {

?5 // ? ? ?Make a choice and add that character to the permutation so far

?6 // ? ? ?Use recursion to rearrage the remaing letters

?7 // }

?8 //

?9 void RecursivePermutation(string sofar, string remain)

10 {

11 ? ? if (remain == "") {cout << sofar << endl; reutrn;}

12?

13 ? ? for (size_t i = 0; i < remain.size(); ++i)

14 ? ? {

15 ? ? ? ? string sofar2 = sofar + remain[i];

16 ? ? ? ? string remain2 = remain.substr(0, i) + remain.substr(i+1);

17 ? ? ? ? RecursivePermutation(sofar2, remain2);

18 ? ? }

19 }

复制代码

?在这个问题中，我们尝试了所有可能的选择，属于穷举递归，总共有n!中排列方法。这是一个非常经典的模式，是许多递归算法的核心，比如猜字谜问题，数独问题，最优化匹配问题，调度问题等都可以通过这种模式解决。

?

【经典穷举问题】子集问题

?问题描述：给定一个集合，列出该集合的所有子集

?

对于每一个决策点，我们从剩余的集合中选择一个元素后，有两种选择，子集包括该元素或者不包括该元素，这样每次递归一步的话，剩余集合中的元素就会减少一个，直到剩余集合为空，我们到达base case。伪代码及C++代码如下：

?

复制代码

?1 // Subset Problem

?2 //

?3 // If there are no more elements remaining, print current subset

?4 // Consider the next element of those remaining

?5 // Try adding it to current subset and use recursion to build subsets from here

?6 // Try not adding it to current subset and use recursion to build subsets from here

?7 void RecursiveSubset(string sofar, string remain)

?8 {

?9 ? ? // base case

10 ? ? if (remain == "") { cout << sofar << endl; return; }

11 ? ??

12 ? ? char ch = remain[0];

13 ? ? string remain2 = remain.substr(1);

14 ? ? RecursiveSubset(sofar, remain2); ? ? ? ?// choose first element

15 ? ? RecursiveSubset(sofar + ch, remain2); ? // not choose first element

16 }

复制代码

?

?

这是另外一个穷举递归的典型例子。每次递归调用问题规模减少一个，然而会产生两个新的递归调用，因而时间复杂度为O(2^n)。这也是个经典问题，需要牢记解决该类问题的pattern，其他与之类似的问题还有最优填充问题、集合划分问题、最长公共子列问题（longest shared subsequence)等。

?

这两个问题看起来很像，实际上差别很大，属于不同的两类问题。在permutation问题中，我们在每次决策点是要选择一个字母包含到当前子串中，我们有n中选择（假设剩余子串长度为n），每一次选择后递归调用一次，因而有n个规模为n-1的子问题，即T(n) = n T(n-1)。而对于subset问题，我们在每个决策点对于字母的选择只能是剩余子串的首字母，而我们决策的过程为选择or not选择（这是一个问题，哈哈），我们拿走一个字母后，做了两次递归调用（对比permutation问题，我们拿下一个字母后只进行了一次递归调用），因此T(n) = 2 * T(n-1)。

?

总结说来：permutation问题拿走一个字母后，递归调用一次，我们的决策点是有n个字母可以拿；而subset问题是拿走一个字母后，进行了两次递归调用，我们的决策点是包括还是不包括该拿下的字母，请仔细体味两者的区别。

?

递归回溯