递归和回溯思想的应用

关键套路初相见：全排列问题

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例：
输入: [1,2,3]
输出: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

拿到一个 n 个数的数组作为入参，穷举出这 n 个数的所有排列方式。

哎？等等，我好像看到一个熟悉的词眼——穷举！楼上是不是说了穷举？我们最近还在哪里见过穷举？是不是在上一节？上一节的哪个位置？DFS 对不对？DFS 用什么实现比较好？递归！好，来得早不如来得巧，我现在就决定用递归来做这个题。

怎么做呢？大家仔细想想，在这个变化的序列中，不变的是什么——是不是坑位的数量？拿示例来说，不管我怎么调整数字的顺序，它们都只能围着这 3 个坑打转。当我们感到变化难以把握时，不如尝试先从不变的东西入手。

现在问题变成了，我手里有 3 个数，要往这 3 个坑里填，有几种填法？我们一个一个坑来看：

• Step1:：面对第一个坑，我有 3 种选择：填 1、填 2、填 3，随机选择其中一个填进去即可。
• Step2：面对第二个坑，由于 Step1 中已经分出去 1 个数字，现在只剩下 2 个选择：比如如果 Step1 中填进去的是 1，那么现在就剩下 2、3；如果 Step1 中填进去的是 2，那么就剩下 1、3。
• Step3： 面对第三个坑，由于前面已经消耗了 2 个数字，此时我们手里只剩下 1 个数字了。所以说第 3 个坑是毫无悬念的，它只有 1 种可能。

我们把三个坑的情况统筹起来，那么全排列就一共有 3x2x1=6 种可能。可惜这道题问的不是全排列的可能性有多少种，而是要求你把每一种可能性都穷举出来。

列举“路径”，我们首先要找到“坐标”。在这道题里，“坐标”就是每一个坑里可能填进的数字。

这里给大家一个思维工具：以后只要分析出重复的逻辑（排除掉类似数组遍历这种简单粗暴的重复），你都需要把递归从你的大脑内存里调度出来、将其列为“可以一试”的解法之一；只要想到递归，立刻回忆我们上一节讲的 DFS 思想、然后尝试套我们这一节末尾教给大家的解题模板。这个脑回路未必 100% 准确，但确实有极高的成功概率——题，是有规律的。这，就是规律之一。

在以上的“填坑”过程中，我们重复地做了以下事情：

• 检查手里剩下的数字有哪些
• 选取其中一个填进当前的坑里

“重复”的内容，就是递归式。

这个重复递归式的动作一直持续到了最后一个数字也被填进坑里为止——“重复”的终点，就是递归边界。

这里大家当然也可以借鉴遍历二叉树的经验 ，通过判断数组的可选数字是否为空，来决定当前是不是走到了递归边界。但是这道题其实可以做得更简单：坑位的个数是已知的，我们可以通过记录当前坑位的索引来判断是否已经走到了边界：比如说示例中有 n 个坑，假如我们把第 1 个坑的索引记为 0 ，那么索引为 n-1 的坑就是递归式的执行终点，索引为 n 的坑（压根不存在）就是递归边界。

递归的编码实现，无非是把我们上面描述过的递归式和递归边界翻译成代码：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 入参是一个数组
const permute = function(nums) {
  // 缓存数组的长度
  const len = nums.length;
  // curr 变量用来记录当前的排列内容
  const curr = [];
  // res 用来记录所有的排列顺序
  const res = [];
  // visited 用来避免重复使用同一个数字
  const visited = {};
  // 定义 dfs 函数，入参是坑位的索引（从 0 计数）
  function dfs(nth) {
    // 若遍历到了不存在的坑位（第 len+1 个），则触碰递归边界返回
    if (nth === len) {
      // 此时前 len 个坑位已经填满，将对应的排列记录下来
      res.push(curr.slice());
      return;
    }
    // 检查手里剩下的数字有哪些
    for (let i = 0; i < len; i++) {
      // 若 nums[i] 之前没被其它坑位用过，则可以理解为“这个数字剩下了”
      if (!visited[nums[i]]) {
        // 给 nums[i] 打个“已用过”的标
        visited[nums[i]] = 1;
        // 将nums[i]推入当前排列
        curr.push(nums[i]);
        // 基于这个排列继续往下一个坑走去
        dfs(nth + 1);
        // nums[i]让出当前坑位
        curr.pop();
        // 下掉“已用过”标识
        visited[nums[i]] = 0;
      }
    }
  }
  // 从索引为 0 的坑位（也就是第一个坑位）开始 dfs
  dfs(0);
  return res;
};

注意

上面这坨代码里，有两个点需要大家格外注意，它们将会成为我们以后做类似题目的关键技巧：

• Map 结构 visited 的使用：填坑时，每用到一个数字，我们都要给这个数字打上“已用过”的标——避免它被使用第二次；数字让出坑位时，对应的排列和 visited 状态也需要被及时地更新掉。
• 当走到递归边界时，一个完整的排列也到手了。将这个完整排列推入结果数组时，我们用了 res.push(curr.slice()) 而不是简单的 res.push(curr) 。为什么这样做？因为全局只有一个唯一的 curr ， curr 的值会随着 dfs 的进行而不断被更新。 slice 方法的作用是帮助我们拷贝出一个不影响 curr 正本的副本，以防直接修改到 curr 的引用。

带着全排列问题教会我们的解题思路和编码技巧，我们再来看另一个类型的题目——组合问题。

组合问题：变化的“坑位”，不变的“套路”

题目描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

示例: 输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路分析

吸取了上一道题的经验，这道题我们应该想到的是：穷举出现了，大概率会用到 DFS。

只要用到 DFS，就不得不想到树形思维方式，进而不得不思考递归式和递归边界的问题。在这个思考的过程中，最重要的一环就是对“坑位”的定位和分析。

从上一道题中，我们不难看出，“坑位”对应的就是树形逻辑中树的某一层，“坑位数”往往意味着递归边界的限制条件。

找“坑位”的思路也是具有规律的：“坑位”往往是那些不会变化的东西。在上一道题中，排列的顺序是变化的，而每个排列中数字的个数却是不变的，因此数字的个数就对应“坑位”的个数；在这道题中，每个组合中数字的个数是不确定的，不变的东西变成了可以参与组合的数字，变化的东西则是每个数字在组合中的存在性。因此我们的思路可以调整为，从每一个数字入手，讨论它出现或者不出现的情况。

root                                            []
数字1——第一层                     1                                   []
数字2——第二层            [1,2]            [1]                   [2]         []
数字3———第三层    [1,2,3]     [1,2]  [1,3]   [1]           [2,3]   [2]   [3]  []

从 root 出发，每一个数字对应树的一层，存在或不存在对应树的两个分叉。从第一层到第三层，我们得到的所有完整路径，就是 3 个数的所有可能的组合形式。

我们分析一下这个过程中的递归式与递归边界：

• 递归式：检查手里剩下的数字有哪些（有没有发现和上一道题的递归式是一样的，因为两道题都强调了数字不能重复使用），选取其中一个填进当前的坑里、或者干脆把这个坑空出来（这里就体现出了和上一道题的区别，这道题强调的是存在性而非顺序）。
• 递归边界：组合里数字个数的最大值。拿示例来说，只给了 3 个数，因此组合里数字最多也只有 3 个，超过 3 个则视为触碰递归边界。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 入参是一个数组
const subsets = function(nums) {
  // 初始化结果数组
  const res = [];
  // 缓存数组长度
  const len = nums.length;
  // 初始化组合数组
  const subset = [];
  // 进入 dfs
  dfs(0);

  // 定义 dfs 函数，入参是 nums 中的数字索引
  function dfs(index) {
    // 每次进入，都意味着组合内容更新了一次，故直接推入结果数组
    res.push(subset.slice());
    // 从当前数字的索引开始，遍历 nums
    for (let i = index; i < len; i++) {
      // 这是当前数字存在于组合中的情况
      subset.push(nums[i]);
      // 基于当前数字存在于组合中的情况，进一步 dfs
      dfs(i + 1);
      // 这是当前数字不存在与组合中的情况
      subset.pop();
    }
  }
  // 返回结果数组
  return res;
};

复盘

• 递归式的变化：在上一道题中，我们检查一个数字是否可用的依据是它是否已被纳入当前排列（ visited 值是否为 1），而这道题中，并不存在一个类似 visited 一样的标记对象。取而代之的，是每次直接以 index 作为了索引起点。这是因为，在排列场景下，一个元素可能出现在任何坑位里；而在组合场景下，坑位的选择逻辑发生了变化，坑位和元素是一一对应的。因此讨论完一个坑位的取舍后，一个元素的取舍也相应地讨论完毕了，直接跳过这个元素的索引往下走即可。
• 递归边界的变化：这道题中，并没有显式的 return 语句来标示递归边界的存在。这个边界的判定被 for 语句偷偷地做掉了： for 语句会遍历所有的数字，当数字遍历完全时，也就意味着递归走到了尽头。

限定组合问题：及时回溯，即为“剪枝”

题目描述：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

思路分析

剪枝：在深度优先搜索中，有时我们会去掉一些不符合题目要求的、没有作用的答案，进而得到正确答案。这个丢掉答案的过程，形似剪掉树的枝叶，所以这一方法被称为“剪枝”。

在这道题中，要做到剪枝，我们需要分别在组合问题的递归式和递归边界上动手脚：

• 递归式：普通组合问题，每到一个新的坑位处，我们都需要对组合结果数组进行更新；这道题中，当且仅当组合内数字个数为 k 个时，才会对组合结果数组进行更新。
• 递归边界：只要组合内数字个数达到了 k 个，就不再继续当前的路径往下遍历，而是直接返回。

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
const combine = function(n, k) {
  // 初始化结果数组
  const res = [];
  // 初始化组合数组
  const subset = [];
  // 进入 dfs，起始数字是1
  dfs(1);

  // 定义 dfs 函数，入参是当前遍历到的数字
  function dfs(index) {
    if (subset.length === k) {
      res.push(subset.slice());
      return;
    }
    // 从当前数字的值开始，遍历 index-n 之间的所有数字
    for (let i = index; i <= n; i++) {
      // 这是当前数字存在于组合中的情况
      subset.push(i);
      // 基于当前数字存在于组合中的情况，进一步 dfs
      dfs(i + 1);
      // 这是当前数字不存在与组合中的情况
      subset.pop();
    }
  }
  // 返回结果数组
  return res;
};

何为“回溯”？

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

有没有发现，这个“回溯算法”和上一节的 DFS ，好像翻来覆去是在讲同一件事情？

实际上，这里的“回溯”二字，大家可以理解为是在强调 DFS 过程中“退一步重新选择”这个动作。这样想的话， DFS 算法其实就是回溯思想的体现。

递归与回溯问题——解题模板总结

什么时候用

看两个特征：

• 题目中暗示了一个或多个解，并且要求我们详尽地列举出每一个解的内容时，一定要想到 DFS、想到递归回溯。
• 题目经分析后，可以转化为树形逻辑模型求解。

为什么这样用

递归与回溯的过程，本身就是穷举的过程。题目中要求我们列举每一个解的内容，解从哪来？解是基于穷举思想、对搜索树进行恰当地剪枝后得来的。

这里需要注意到另一种问法：不问解的内容，只问解的个数。这类问题往往不用 DFS 来解，而是用动态规划（我们后面会学）。这里，大家先记下这个辨析，对以后做题会有帮助。

怎么用

• 一个模型——树形逻辑模型；
• 两个要点——递归式和递归边界。

树形逻辑模型的构建，关键在于找“坑位”，一个坑位就对应树中的一层，每一层的处理逻辑往往是一样的，这个逻辑就是递归式的内容。至于递归边界，要么在题目中约束得非常清楚、要么默认为“坑位”数量的边界。

用伪代码总结一下编码形式，大部分的题解都符合以下特征：

function xxx(入参) {
  前期的变量定义、缓存等准备工作

  // 定义路径栈
  const path = []

  // 进入 dfs
  dfs(起点)

  // 定义 dfs
  dfs(递归参数) {
    if(到达了递归边界) {
      结合题意处理边界逻辑，往往和 path 内容有关
      return
    }

    // 注意这里也可能不是 for，视题意决定
    for(遍历坑位的可选值) {
      path.push(当前选中值)
      处理坑位本身的相关逻辑
      path.pop()
    }
  }
}