前端学数据结构与算法（十三）：01执行的艺术 - 回溯算法(上)

前言

在最初尝试学习算法时，对两个算法留下了深刻的印象，一个是动态规划，另一个就是回溯算法。如果说算法思想的艺术，那归于动态规划；但如果说用计算机执行机制解决问题的艺术，那非回溯算法莫属了，也由衷的赞叹，原来计算机还能这么执行。

什么是回溯算法？它能解决什么问题？带着这两个问题，然后用示例来回答这几个问题是本章的目的。

回溯算法是建立在递归之上，虽说第四章已经详细说明了递归的执行机制，但例子都是简单的单递归形式。所以本章首先复习下递归，之后层层递进，最后直至解决回溯的代表问题N皇后，逐步彻底搞懂回溯算法。闲言少叙，一起来认识这么酷的算法吧。

什么是回溯算法？

我想每个人都希望自己拥有回到过去的能力，如果当时选择勇敢的追她，也许现在就没遗憾了吧？如果当时能好好学习，现在也不至于被学历卡脖子了？如果当时听父母的留在老家，现在也不至于这么累吧？每一个选择的背后，都是舍弃掉其他选择的可能性，也就是选择的机会成本。

回到算法，那有没可能上述三个选择我都做了，最后我还把它们选择之后的结果进行比较，选择最满意的那个。可以！回溯恰恰就是能把每种可能性都尝试的算法，这是一种暴力搜索算法，它可以对问题每个不同的分支进行尝试，不要说人生的十字路口，就是米字路口我也把每种结果给你整明白。

回溯算法能解决什么问题？

回溯算法能进行暴力的搜索，那它到底具体能解决什么问题? 它解决的问题是需要暴力才能解决的问题-_-#, 以下列举回溯能解决的六种常见问题类型。

1. 组合问题

比如请给出数字[1, 2, 3, 4]两两组合的每种可能性，结果就是[12, 13, 14, 23, 24, 34]，因为23和32是一个组合，所以忽略32。如果你说这个很简答了，使用循环也可以解决，那题目条件换一下，给出数字1 - 20之间每12种组合的可能性，这时遍历就不好使了。

2.排列问题

给出[1, 2, 3]所有的全排列的可能性，结果就是[123, 132, 213, 231, 312, 321]。

3.子集问题

给出数字[1, 2, 3]所有的子集(幂集)的可能性，结果就是[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]。

4.分割问题

给出一个数字字符串25525511135，返回它所有组成IP地址格式的可能，结果就是["255.255.11.135", "255.255.111.35"]。

5.floodFill填色问题

问题类型参考力扣200岛屿和547朋友圈，之后详细介绍。

6.棋盘问题

类型参考解数独和8皇后问题，之后详细介绍。

上述的六种类型看着区别可能挺大，其实它们都是树型问题这个类型，这个到具体问题讲解时再说明其中的道道。

再次理解递归

因为回溯是建立在递归之上，也可以说回溯就是递归，只是递归更复杂些的调用，所以我们还是先用两个题目重新理解下的递归调用。

1480 - 一维数组的动态和 ↓

给你一个数组 nums , 请返回 nums 的动态和。 输入：nums = [1,2,3,4] 输出：[1,3,6,10] 解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/running-sum-of-1d-array 

简单来说，就是依次累加的过程，每一个数字的和，等于它之前所有的元素加上自身的和。从前往后使用一次遍历解决：

var runningSum = function (nums) { for (let i = 0; i < nums.length - 1; i++) { nums[i + 1] = nums[i + 1] + nums[i] } return nums }; 

此时我们开始折腾，如果是使用递归如何解决这个问题？其实上面的描述：每一个数字的和，等于它之前所有元素加上自身的和已经将子问题进行的拆解。所以此时我们可以倒推，数组最后一个数字的和就等于它之前所有的和加上自身，再依次往前倒推后，代码如下：

var runningSum = function (nums) { const _helper = end => { if (end === 0) { // 到数组头了，开始归 return nums[0] } nums[end] = _helper(end - 1) + nums[end] // 它前面的元素加自身 return nums[end] // 返回计算后的结果 } _helper(nums.length - 1) // 从最后一个数字开始 return nums }; 

这是最简单的单递归调用，也就是说递归函数里只调用自身一次，接下来看一个调用自身两次的问题。

22 - 括号生成 ↓

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。 输入：n = 3 输出： [ "((()))", "(()())", "(())()", "()(())", "()()()" ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/generate-parentheses 

根据题意可知，最终的长度一定是2n，且左括号和右括号的个数分别是n，且必须以左括号作为有效括号的起始，只有右括号的剩余数量大于左括号时才能放置，先看代码，我画了一个执行顺序图，大家对比看看：

var generateParenthesis = function (n) { const ret = [] // 存放有效的括号集合 const _helper = (left, right, parenthesi) => { if (left === 0 && right === 0) { // 当左右括号的数量都用完时 ret.push(parenthesi) // 找到了一个有效的集合 } if (left > 0) { // 放左括号的规则：当还有左括号时就可以进行放置 _helper(left - 1, right, parenthesi + '(') // 减少左括号的数量 } if (right > left) { // 放右括号的规则：当右括号的剩余数量大于左括号时才能放置 _helper(left, right - 1, parenthesi + ')') // 减少右括号的数量 } } _helper(n, n, '') // 传入左括号和右括号的剩余数量 return ret }; 

图中灰色的节点是部分剪枝的操作，因为只要是按照灰色节点添加括号，后续的生成必然是不合规的，所以在代码里直接不执行后续的递归即可。

还有就是这个函数是两次递归调用自身，首先是先执行添加左括号的递归，当左括号已经添加完时，再开始执行添加右括号的递归，注意观察第6步到第7步的跳跃，因为递归是调用自身两次，第2步到第3步只是执行了其中的一种可能性，因为是深度优先遍历，当这个可能性已经执行完毕时，就需要跳跃到第7步执行另一种可能性，之后的每个函数遵循这样的规则，这也是递归的执行机制。

不难发现，当递归每一步的可能性是两次时，最终的执行顺序生成的就是一颗二叉树，递归的深度取决于最终结果的长度，结果是2n长度，所以深度就是2n。

回溯算法是啥？就是把这里的可能性2次，换成n次，从而把二叉树会变成n叉树，而且在每次递归之后再执行另外的操作，此时就是树的后序遍历执行的时机。

组合问题

组合排列经常一起出现，这里先简单说明下它们的区别。

什么是组合？假设有三个明星abc，有三位粉丝xyz，让每位粉丝在其中选2位认可的明星，有多少选法？很明显粉丝选ab或ba都无所谓，最终的结果里，这两种选择是一样的，所以这就是组合问题。

什么是排列？还是假如有三个明星abc，有三位粉丝xyz，让每位粉丝选出你认为的第1名和第2名，有多少种选法？很明显此时ab和ba就是两种不同的结果，都需要统计，这就是排列问题。

17 - 电话号码的字母组合 ↓

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number 

以输入23为例，就是把2对应的abc都分别提取出来，去和3对应的def进行组合。我们需要一个辅助函数来帮助我们这件事，它做的事就是把数字对应的字母取出来，用取出来的字母，去和下一个数字对应的字母进行组合，最终找到所有组合。

什么时候算是找到了一个符合要求的组合？当这个组合的长度等于输入数字的长度时，就算是找到了一个。

因为每一个数字平均代表的就是3个字母，所以用递归来表示执行树时，就会是一颗三叉树。递归的深度是多少？取决于输入的数字的个数，例如当输入27465五个数字时，最终执行树的深度就是5层。

代码如下：

const letterCombinations = digits => { if (digits === '') { // 当输入空字符串时 return [] // 返回空集合 } const ret = [] // 用于存放所有找到的组合 const letterArr = [' ', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'] // 存放数字对应的字母表 const _helper = (start, s) => { // 辅助函数 if (s.length === digits.length) { // 找到了一个组合 ret.push(s) return // 返回上一层递归 } const letters = letterArr[digits[start]] // 对应的就是abc, def for (let i = 0; i < letters.length; i++) { _helper(start + 1, s + letters[i]) // 执行多次递归 } } _helper(0, '') return ret }; 

传入的参数start，表示的是需要依次处理的输入数字的下标。以23为例，首先处理下标0也就是2对应字母问题，在进入下一层递归时+ 1，是为了处理3对应的字母组合问题。

传入的s表示的是当前组合，每次进入下一层递归时的s + letters[i]，就是带着这一层的结果进行下一层。即使这一层已经符合组合的要求，也是在下一层的递归终止条件进行结果的保存，然后终止递归，回到上一层递归。

因为每一层的递归都是循环的执行n次，所以当本层循环执行完，才会返回上一层。

77 - 组合 ↓

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [[1,2],[1,3],[1,4],[2,4],[2,3],[3,4]] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combinations 

有了上一个组合问题的解决经验后，我们直接上执行树，再来解释这题的异同点，以1 ... 4，且k为2为例：

例如13和31是同一个组合，所以在处理时，我们需要忽略'相同'的组合，如何进行忽略操作？每次进入下一层递归时，起始的遍历的位置都进行+ 1即可。其余的逻辑与上一题类似，代码如下：

var combine = function (n, k) { if (n < 0 || k < 0 || k > n) { // n和k都得是符合条件的 return [] } const ret = [] const _helper = (start, arr) => { if (arr.length === k) { ret.push(arr) return } for (let i = start; i <= n; i++) { // i = start，忽略比start小的数进行组合 _helper(i + 1, arr.concat(i)) } } _helper(1, []) return ret }; 

这个解法确实能获得通过，但是好家伙，这也太慢了吧。原因就出在我们进入下一层递归的核心逻辑上：

_helper(i + 1, arr.concat(i)) 

没想到concat这个方法会这么慢，其实我们的目的无非就是把当前的数字i加入到数组里，然后带入到下一层递归去，所以我们可以使用push方法。

同时也有一点，从执行树不难发现，最后去找另外一个组合时，需要将之前组合的末尾弹出才行，需要留出位置。所以我们在每次循环后，进行弹出留位置操作。优化如下：

var combine = function (n, k) { if (n < 0 || k < 0 || k > n) { return [] } const ret = [] const _helper = (start, arr) => { if (arr.length === k) { ret.push([...arr]) // 需要进行拷贝 return } for (let i = start; i <= n; i++) { arr.push(i) _helper(i + 1, arr) arr.pop() } } _helper(1, []) return ret }; 

在终止条件那里找到了一个符合的组合时，我们需要进行一次拷贝，因为每一层的循环都有arr.pop()操作，最终会影响所有收集到的组合。来看下优化后的结果：

39 - 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ， 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。  输入：candidates = [2,3,6,7], target = 7, 所求解集为：[[7], [2,2,3]] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum 

这题有几个关键信息，首先是多了一个target目标值，也就是说我们每次统计的值需要与这个目标值进行比对，一个对比较很有帮助的操作就是首先对candidates进行排序，这样的话就可以将计算结果进行保存起来，只在它的基础进行加减即可。

还有一个信息是可以无限制的使用数组里的某个数，排序之后这个操作也会很方便，直接从最小的数开始统计每种组合的可能。

剩下的解题框架和上一题是类似的，我们写出来代码如下：

var combinationSum = function (candidates, target) { candidates.sort((a, b) => a - b) const ret = [] const _helper = (start, sum, arr) => { if (sum > target) { // 因为是排好序的，所以sum接下来只会更大 return } if (sum === target) { // 正好找到了 ret.push([...arr]) return } for (let i = start; i < candidates.length; i++) { sum += candidates[i] // sum为计算结果 arr.push(candidates[i]) // arr存放暂存的集合 _helper(i, sum, arr) // 注意第一个参数没有+ 1，因为要无限使用 sum -= candidates[i] arr.pop() } } _helper(0, 0, []) return ret }; 

有两个递归结束条件，如果是大于那就结束当前层递归，结束之后sum -= candidates[i]，减去candidates[i]这个不合规或已经被使用的值，然后弹出candidates[i]，进入下一次循环。

其实和上一题的解题思路是一致的，只是说多了一些解题的限制条件而已。

最后

回溯算法的复杂度我们还没有分析，这里简单的说明下。其实从之前的题目不难发现，回溯算法的复杂度非常高。例如17题，如果输入5个数字，那么最终执行树展开最下一层的节点就是3 * 3 * 3 * 3 * 3个，这个数据规模是指数级别的O(2ⁿ)。所以在处理大数据时回溯对计算机计算性能要求非常高，而回溯算法也有其特有剪枝操作来减少无谓的计算量。

回溯算法这个题目很广，剩下的几种题型再下一章进行讲解。