回溯 - 1. 组合（77） - 《前端知识库》

一、题目内容中等
二、解题思路
三、具体代码
- 无剪枝版
- 剪枝版
四、其他解法

力扣题目链接

一、题目内容中等

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例1：

输入：n = 4, k = 2 输出： [
[2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

示例2：

输入：n = 1, k = 1 输出：[[1]]

提示：

1 <= n <= 20
1 <= k <= n
二、解题思路
暴力 for 循环失效
本题这是回溯法的经典题目。
直接的解法当然是使用 for 循环，例如示例中 k 为 2，很容易想到用两个 for 循环，这样就可以输出和示例中一样的结果。
```
var n = 4;
var res = [];
for(var i = 0;i <= n;i++) {
  for(var j = i + 1;j <= n;j++) {
    res.push([i, j]);
}
}
```
输入：n = 100，k = 3，那么就要三层 for 循环，代码如下
```
var n = 100;
var res = [];
for(var i = 0;i <= n;i++) {
  for(var j = i + 1;j <= n;j++) {
  for(var u = j + 1;u <= n;u ++) {
        res.push([i, j, u]);
  }
}
}
```
如果 n 为 100，k 为 50 呢，那就 50 层 for 循环，是不是开始窒息。
此时就会发现虽然想暴力搜索，但是用 for 循环嵌套连暴力都写不出来！

使用回溯法思路

那么回溯法怎么暴力搜呢？
上面我们说了要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。

我们把组合问题抽象为如下树形结构：

可以看出这个棵树，一开始集合是 1，2，3，4，从左向右取数，取过的数，不在重复取。
第一次取 1，集合变为 2，3，4 ，因为 k 为 2，我们只需要再取一个数就可以了，分别取 2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中可以发现n相当于树的宽度，k相当于树的深度。

那么如何在这个树上遍历，然后收集到我们要的结果集呢？
图中每次搜索到了叶子节点，我们就找到了一个结果。

相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

回溯法三部曲

1. 递归函数的返回值以及参数

在这里要定义两个全局变量，一个用来存放符合条件结果的集合，一个用来存放符合条件结果。
代码如下：

  let res = [];  // 存放符合条件结果的集合
  let path = []; // 用来存放符合条件结果

其实不定义这两个全局遍历也是可以的，把这两个变量放进递归函数的参数里，但函数里参数太多影响可读性，所以定义全局变量了。

函数里一定有两个参数，既然是集合n里面取k的数，那么n和k是两个int型的参数。
然后还需要一个参数，为 int 型变量 startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n]）

为什么要有这个 startIndex 呢？
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。

从下图中红线部分可以看出，在集合[1,2,3,4]取 1 之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是 startIndex。

所以需要 startIndex 来记录下一层递归，搜索的起始位置。
那么整体代码如下：

let res = [];  // 存放符合条件结果的集合
let path = []; // 用来存放符合条件结果
const backTracking = (n, k, startIndex) => {}

2. 回溯函数终止条件

纵向遍历

什么时候到达所谓的叶子节点了呢？
path 这个数组的大小如果达到 k，说明我们找到了一个子集大小为 k 的组合了，在图中 path 存的就是根节点到叶子节点的路径。
如图红色部分：

此时用 res 二维数组，把 path 保存起来，并终止本层递归。
所以终止条件代码如下：

if (path.length == k) {
    res.push(path);
    return;
}

横向遍历（单层搜索的过程）

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出 for 循环用来横向遍历，递归的过程是纵向遍历

如此我们才遍历完图中的这棵树。
for 循环每次从 startIndex 开始遍历，然后用 path 保存取到的节点i。
代码如下

for (let i = startIndex;i <= n;i++) { // 控制树的横向遍历
    path.push(i); // 处理节点 
  backTracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i + 1开始
  path.pop();  // 回溯，撤销处理的节点
}

回溯优化：剪枝

这个遍历的范围是可以剪枝优化的，怎么优化呢？
来举一个例子，n = 4，k = 4 的话，那么第一层 for 循环的时候，从元素 2 开始的遍历都没有意义了。
在第二层 for 循环，从元素 3 开始的遍历都没有意义了
这么说有点抽象，如图所示：

图中每一个节点（图中为矩形），就代表本层的一个 for 循环，那么每一层的 for 循环从第二个数开始遍历的话，都没有意义，都是无效遍历。
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果 for 循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。

注意代码中 i ，就是 for 循环里选择的起始位置

for (let i = startIndex; i <= n; i++)

接下来看一下优化过程如下：

已经选择的元素个数：path.length;
还需要的元素个数为: k - path.length;
在集合 n 中至多要从该起始位置 : n - (k - path.length) + 1，开始遍历

为什么有个 +1 呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3，目前已经选取的元素为0（path.length为 0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2
从 2 开始搜索都是合理的，可以是组合 [2, 3, 4]。

for(let i = startIndex;i <= n - k + 1 + path.length; i++)

三、具体代码

无剪枝版

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  let res = [];
  let path = [];
  const backTracking = (n, k, startIndex) => {
    if (path.length === k) {
      res.push(path.map(i => i));
      return;
    }
    for (let i = startIndex; i <= n; i++) {
      path.push(i);
      backTracking(n, k, i + 1);
      path.pop();
    }
  }
  backTracking(n, k, 1);
  return res;
};

剪枝版

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  let res = [];
  let path = [];
  const backTracking = (n, k, startIndex) => {
    if (path.length === k) {
      res.push(path.map(i => i));
      return;
    }
    for (let i = startIndex; i <= (n - k + path.length + 1); i++) {
      path.push(i);
      backTracking(n, k, i + 1);
      path.pop();
    }
  }
  backTracking(n, k, 1);
  return res;
};

1. 组合（77）

一、题目内容 中等

二、解题思路

暴力 for 循环失效