如何尝试走迷宫？遇到障碍时，“原路返回”从头继续探索。这是回溯算法的形象解释。更抽象一点，回溯算法可以理解为对一棵树的深度遍历，每个叶子节点都是一个方案的最终状态，某条路由的判断可能在访问到叶子节点之前就结束了。与动态规划相比，回溯可以解决更复杂的问题，尤其是对于有后效的问题。动态规划之所以不能处理aftereffect的问题，是因为它的dp(i)=F(dp(j))where0<=j0)func(restParams,results.concat(currentResult));}这里的params就像迷宫下面的路线，结果记录了走过的最佳路线。当params路由用完后，就走出迷宫，否则终止，让其他递归继续。所以回溯逻辑其实很容易写。难点在于如何判断这道题应该用回溯来做，以及如何优化算法的复杂度。先从两个入门题开始，分别是电话号码的字母组合和IP地址的恢复。电话号码的字母组合电话号码的字母组合是一道中等题，题目如下：给定一个只包含数字2-9的字符串，返回它能代表的所有字母组合。可以按任何顺序返回答案。数字到字母的映射如下（与电话键相同）。请注意，1不对应任何字母。电话号码对应的字母其实就是一个映射表。例如，2个映射a、b、c和3个映射d、e、f。那么2,3就可以表示3x3=9个字母组合，要打印出如ad,ae的组合必须使用穷举法，这也是一种回溯，但是需要每一种可能，更复杂的回溯可能不满足每条路径的要求。所以这道题很好做，只要构造出所有可能的组合即可。接下来，我们来看一个类似的问题，但是具有一定的法律判断分支，来恢复IP地址。恢复IP地址恢复IP地址是一个中等水平的问题。题目如下：给定一个只包含数字的字符串来表示一个IP地址，返回所有可能从s获得的有效IP地址。您可以按任何顺序返回答案。一个有效的IP地址恰好由四个整数组成（每个整数介于0和255之间，不带前导0），以“.”分隔。例如：“0.1.2.201”和“192.168.1.1”是有效的IP地址，而“0.011.255.245”、“192.168.1.312”和“192.168@1.1”是无效的IP地址。首先，必须一一阅读。问题是一个字符串可能代表多个可能的IP。例如，25525511135可以表示为255.255.11.135或255.255.111.35。原因是11.135和111.35是合法的表示，所以我们必须使用回溯的方法来解决问题，但是在回溯的过程中，它会根据读取到的数据，动态判断新增哪些分支，哪些分支是非法的。比如读取[1,1,1,3,5]时，由于11和111都是合法的，所以这个位置的数字只需要在0到255之间，而1113超出了这个范围，所以忽略，所以从这个场景分出两条路：当前项：11，剩余项135。当前项：111，剩余项35。然后递归，直到终止非法情况，比如有4项但还有剩余数，或者IP范围不满足等等。可见，只要把合法和非法的情况梳理清楚，直到如何动态生成新的递归判断，这道题就不难了。这道题的输入很直接，直接给出。事实上，并不是每一个问题输入都那么容易思考。让我们看看接下来的完整安排。全排列全排列是一个中级问题。题目如下：给定一个没有重复数字的数组nums，返回它所有可能的全排列。您可以按任何顺序返回答案。和还原IP地址类似，我们也消费给定的输入，比如123，我们可以先消费1，剩下的23继续组合。但是和IP还原不同的是，第一个数可以是123中的任意一个，所以在生成当前项的时候其实是不一样的：可以从剩余的所有项中选择当前项，然后递归。比如第一次123，可以选择1或者2或者3，如果是1的话，还剩23，那么下次可以选择2或者3。当只剩下一项时，你不需要选择。全数组的输入虽然不像恢复IP地址的输入那么直接，但好歹也是根据给定的字符串推导的。对于更复杂的主题，输入可能会被分解成多个部分。这就需要你灵活的思考了。例如，括号生成标题。括号生成括号生成是一个中级问题。题目如下：数字n代表生成括号的对数。请设计一个函数，可以生成所有可能且有效的括号组合。示例：输入：n=3输出：["((()))","(()())","(())()","()(())","()()()"]这道题的基本思路和上一道题很相似，而且由于这道题问的是所有的可能性，不是最优解，所以不能使用动态规则，所以考虑回溯算法。上一题IP的输入是已知字符串，这道题的输入需要你动动脑筋。这个问题的输入是字符串吗？显然不是，因为输入的是括号的个数，那么一个括号的个数就够了吗？还不够，因为标题需要有效括号，那什么是有效括号呢？是闭的，所以我们想到用左右括号的个数来表示这个数，也就是输入为n，那么转化为open=n，close=n。有了输入，如何消费输入？我们可以在每一步使用一个左括号open或者一个右括号close，但是第一个必须是open，并且当前消耗的close数必须小于消耗的open数，然后我们可以加上close，因为必须有一个closeonleftopen形成一个合法的闭包。所以这个问题很容易解决。回过头来看，回溯的输入参数一定要能够灵活的思考，而这个思考要看你的经验。比如遇到括号问题，你会下意识地拆解成左右括号。因此，算法是相通的，适当的知识传递可以事半功倍。好了，说到这里，其实并不是所有的问题都可以通过回溯来解决，但是有些问题看起来只是回溯问题的变种，其实不然。让我们回到上一个全排列问题，它与下一个排列更相似。这道题好像是从全排列推导出来的，但是回溯算法是解决不了的。我们来看看这个问题。下一个排列下一个排列是一个中级问题。题目如下：为了实现获取下一个排列的功能，该算法需要将给定的数列按照字典顺序重新排列成下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列为最小的排列（即升序）。必须就地修改，只允许额外的常量空间。例如：输入：nums=[1,2,3]输出：[1,3,2]输入：nums=[3,2,1]输出：[1,2,3]如果你在想，你能不能从中吸取教训？全排列的思想，下一个排列自然是在全排列的过程中推导出来的，大概率是想不出来的，因为从整体推到部分的效率太低了，这道题直接给出一个局部值，我们必须使用相对“局部方法”快速推导出下一个值，所以这个问题不能用回溯算法来解决。对于3,2,1的例子，由于已经是最大的排列，接下来的排列只能是1,2,3的初始升序，属于特例。另外，还有下一个更大的排列，以1,2,3为例，更大的是1,3,2，而不是2,1,3。我们看一个更长的例子，比如3,2,1,4,5,6。我们可以发现不管前面的顺序怎么降，只要后面几个是升序的，把后面两个倒过来就行了：3、2、1、4、6、5。3、2、1、4、5、6、9、8、7呢？显然任何相邻的9,8,7交换都会使数字变小，这不符合要求，我们仍然要交换5,6..而不是6,9，因为65x比596大得多。这里我们得到一个几条规则：尽量交换以下号码。交换5,6会比交换6,9大，因为6,9更靠后，位数更少。我们把3,2,1,4,5,6,9,8,7分成两段，分别是前段3,2,1,4,5,6和后段9,8,7，我们想要让前段尽可能大的数和后段尽可能小的数交换，同时又要保证后段的数比后段尽可能小前面部分中的数字尽可能大。为了满足第二点，我们必须从后往前查找。如果是升序，则跳过它，直到找到一个小于j-1的数j。然后第一部分交换第j项，第二部分找最小的数。作为交换，由于搜索算法的原因，后段必须是降序排列，所以从后往前找出第一个大于j的项进行交换。最后我们发现交换后下一项可能并不完美，因为后面的部分是降序的，而我们把前面尽可能小的“大”位改了，下一个顺序必须是升序到满足接下来的安排。因此，后面的部分应该按升序排列。因为后面已经满足了降序，所以可以采用双指针交换的方式，相互交换成为升序。这一步不要使用快速排序，这样会使整体时间复杂度增加O(nlogn)。最后，由于只进行了一次扫描+一次反转后段，算法的复杂度为O(n)。从这道题可以发现，千万不要小看看似变异的题。从全排到下排，可能需要彻底改变思路，而不是优化回溯。让我们继续回到回溯问题。最经典的回溯问题是N皇后，也是最难的问题。与之类似的还有数独题的解法，但都是大同小异。这次我们还是以NQueen为代表来了解一下。NQueensProblemNQueensproblem是一道难题，题目如下：nQueensproblem研究如何在n×n的棋盘上放置n个皇后，并防止皇后互相攻击。给定一个整数n，返回n个皇后问题的所有不同解。每个解决方案都包含针对n皇后问题的不同棋子放置方案，其中“Q”和“.”分别代表皇后区和开放空间。女王的攻击范围很广，横、竖、斜都有，所以当n<4时无解，当魔法时n>=4有解。比如下面两张图：这道题明显有“强”的后遗症，因为皇后的攻击范围是由它的位置决定的。也就是说，一个皇后的位置确定后，其他皇后可能的放置位置都会发生变化，所以只能使用回溯算法。那么如何识别合法和非法地点呢？核心是根据横竖斜三种攻击方式建立四个数组，分别存储哪些行列左右位置不能放置，然后将所有合法的位置作为下一次递归的可能位置，直到thequeen完成，或者直到没地方放为止。很容易想到四个数组，分别存放占用的下标。这样的话，递归中的条件判断分支就比较复杂了，其他的其实都不难。这道题空间复杂度的进阶算法是用二分法将四个下标数组替换成4个数。每个数组转换成二进制时，1的位置代表占用，0的位置代表未占用。位操作可以更快、更低成本地进行位置占用，判断当前位置是否被占用。这里只是举一个例子，大家可以感受下二进制的魅力：由于一行中只能放置一个皇后，所以每次都会从下一行开始，所以不需要看行数限制（at至少下一行不能与上一行相同）。行冲突），所以我们只需要记录列、左、右三个位置。不同的是我们用的是二进制数，只要三个数就可以表示行、左、右。二进制位为1表示占用，0表示未占用。例如column、left、right分别是变量x、y、z，对应的二进制可能是：000000100100000001100。“非”逻辑是任意1都是1，所以“非”逻辑可以将所有1组合起来,即x|是|z0011101。然后将结果取反，使用非逻辑，即~(x|y|z)，结果为1100010，那么这里的全1表示可以放置的位置，我们记这个变量为p，并继续通过p&-p取最后一个1得到放置位置，然后调用递归。从这道题可以发现，N皇后的难点不在于回溯算法，而在于如何用二进制写出高效的回溯算法。因此，对回溯算法的考察比较全面，因为算法本身非常有规律，也比较“笨拙”，所以更需要把重点放在优化效率上。总结回溯算法本质上是利用计算机的高速运算能力来尝试所有的可能性。唯一不同的是比较暴力的解法可能会在某个分支提前终止（分支剪枝），所以其实是一个比较繁琐的算法。它应该只在它有后遗症时使用，并且不能使用像下一个排列这样的贪婪或聪明的解决方案。最后，我们要总结和比较回溯和动态规划算法。事实上，动态规划算法的剧烈递归过程相当于回溯，但动态规划可以使用缓存来存储之前的结果，避免重复子问题的重复计算。问题有后遗症，没有重复的子问题，所以不能使用缓存加速，所以回溯算法的高复杂度在所难免。回溯算法被称为“万能解题法”，因为它可以解决很多大规模的计算问题，是利用计算机计算能力的良好实践。讨论地址为：Jingdu《算法 - 回溯》·Issue#331·dt-fe/weekly想参与讨论的请戳这里，每周都有新话题，周末或周一发布。前端精读——帮你过滤靠谱的内容。关注前端精读微信公众号版权声明：免费转载-非商业-非衍生-保留署名（知识共享3.0许可）
