题目

给定两个整数 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 循环，例如示例中 k 为 2 ，很容易想到，用两个 for 循环，这样就可以输出和示例中一样的结果。代码如下：

int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        cout << i << " " << j << endl;
    }
}

输入：n = 100, k = 3 那么就三层for循环，代码如下：

int n = 100;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int u = j + 1; u <= n; n++) {
            cout << i << " " << j << " " << u << endl;
        }
    }
}

如果 n 为 100 ，k 为 50 呢，那就 50 层 for 循环，是不是开始窒息。此时就会发现虽然想暴力搜索，但是用 for 循环嵌套连暴力都写不出来！

那么我们就可以用回溯法来解决嵌套层数的问题。因为回溯法是用递归来做层叠嵌套的（可以理解是开 k 层 for 循环），每一次的递归中嵌套一个 for 循环，那么递归就可以用于解决多层嵌套循环的问题了。

例如：n 为 100 ，k 为 50 的情况下，就是递归 50 层。

这也是为什么在回溯算法理论基础这一篇文章中说“回溯的本质是穷举，并不是什么高效的算法。”的原因。

此外， 回溯算法理论基础 中提到，回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了。

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

可以看出这个棵树，一开始集合是 1，2，3，4，从左向右取数，取过的数，不在重复取。

第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。

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

那么如何在这个树上遍历，然后收集到我们要的结果集呢？
图中每次搜索到了叶子节点，我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来，就可以求得 n 个数中 k 个数的组合集合。

下面我们按照回溯算法理论基础里提到的算法模板回溯法三部曲开始正式讲解代码了。

回溯法三部曲

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

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

List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>(); // 用来存放符合条件结果

void backtracking(int startIndex)

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

既然是集合 n 里面取 k 个数，那么 n 和 k 是两个 int 型的常量参数，同样也可以放到全局变量中。

然后还需要一个参数，为 int 型变量 startIndex ，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。

为什么要有这个 startIndex 呢？

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠 startIndex 。

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

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

int n, int k; // 题目常量参数
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件单一结果
void backtracking(int startIndex)

2、回溯函数终止条件

什么时候到达所谓的叶子节点了呢？

path 这个链表的大小如果达到 k ，说明我们找到了一个子集大小为 k 的组合了，在图中 path 存的就是根节点到叶子节点的路径。如图红色部分：

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

if (path.size() == k) {
    result.add(new ArrayList<>(path));
    return;
}

3、单层搜索的过程

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

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

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

}

可以看出 backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。

backtracking 的下面部分就是回溯的操作了，撤销本次处理的结果。至此关键地方都讲完了。整理上面的思路，可以得到如下代码：

class Solution {
    private int n = 0, k = 0;

    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        backTracking(1);
        return result;
    }

    private void backTracking(int startIndex) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            backTracking(i + 1);
            path.removeLast();
        }
    }
}

还记得在回溯算法理论基础里给出的回溯法模板么？

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

对比一下本题的代码，是不是发现有点像！ 所以有了这个模板，就有解题的大体方向，不至于毫无头绪。

到这里其实还没算完，还有一步剪枝我们没有做。

剪枝

我们在回溯算法理论基础里说过，回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的。

在遍历的过程中有如下代码：

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

}

这个遍历的范围是可以进一步优化的。

举一个例子，n = 4，k = 4 的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。在第二层for循环，从元素3开始的遍历都没有意义了。这么说有点抽象，如图所示：

图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果 for 循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。

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

for (int i = startIndex; i <= n; i++) {

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

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

为什么有个 +1 呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3，目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。
这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。

所以优化之后的for循环是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

经过剪枝后，我们得到了最终答案。

答案

Java

class Solution {
    // 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合
    int n, k;

    // 结果集
    List<List<Integer>> result = new ArrayList<>();
    // 搜索路径
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;

        backtracking(1);

        return result;
    }

    // 填第 startIndex 位数字
    private void backtracking(int startIndex) {
        // 终止条件
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 如果 for 循环选择的起始位置（startIndex）之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
        // 来举两个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。

        // 若此分支不减
        // 1. 已经选择的元素个数：path.size()
        // 2. 还需要的元素个数为: k - path.size()
        // 3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            // 选择一个数
            path.add(i);
            // 递归选择下一个数
            backtracking(i + 1);
            // 撤销本次选择的数
            path.removeLast();
        }
    }
}

REF

https://programmercarl.com/0077.组合.html
https://leetcode-cn.com/problems/combinations/

算法总纲

77. 组合

题目