前端学数据结构与算法（十三）：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
};

image

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

还有就是这个函数是两次递归调用自身，首先是先执行添加左括号的递归，当左括号已经添加完时，再开始执行添加右括号的递归，注意观察第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

image

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

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

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

image

代码如下：

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为例：

image

例如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
};

image

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

_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()操作，最终会影响所有收集到的组合。来看下优化后的结果：

image

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ⁿ)。所以在处理大数据时回溯对计算机计算性能要求非常高，而回溯算法也有其特有剪枝操作来减少无谓的计算量。

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