[数据结构与算法]【每日一题】77. 组合

题目

题目链接：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

解题思路

👉递归

可能你的第一想法是暴力 k 个循环，但是看到 n 的取值就会沉默了。所以会立马想到另一种思路：递归

递归的深度为：k ，宽度为 n 。这应该是理所应当的想到吧，因为 k 的值是变的，无法用 k 确定用几层循环，那就把 k 变成递归的深度，这样可以直接有一个返回条件了：当 k 等于 0 时。后面的思路应该做了一定量的递归题就直接不假思索的写出来了。循环遍历 n 个数进入递归函数中，递归结束后将其弹出。当 k 等于 0 时，就是数组达到 k 个值，将数组的值存入即可。

• 递归函数的参数

  • n ，这个值不传入那递归的宽度就没了
  • k ，这个值也是必须的
  • m ，由于放入数组的数字组合不能重复，所以每次循环都要是上一个数字的后面一位，所以需要一个数存储当前遍历到哪个数

• 递归函数的条件

  已经知道了是 k 等于 0 时，且此时将数字的组合存入数组中

• 递归函数的功能

  遍历从 m 到 n 的数字，将其放入数组中，且将其数字传入下一个递归

👉优化

对于上面的递归，还有一个剪枝的地方：遍历到当前位置的数字 m 距离 n 的大小比剩余需要的数字个数 k 小时，或者说即使把剩余所有的数字都放入数组中都不能让数字个数达到 k 时，就可以直接返回了。

👉字典序法

官方给了另一种难理解的方法，用二进制数表示选中的数字，然后通过改变二进制数字达到 k 个数字的组合。这种方法我大概讲一下吧，因为不仅难理解而且时间复杂度和递归是一样的，所以选择性的看吧。

用 n 位二进制数表示选中的数字（所有的数字都按降序排序），当二进制数字里的一位是 1 时，表明选中了该数字，这就是一种组合，通过改变 n 位二进制数，从而选中不同的数字进行组合。改变的方式：

• 该二进制数的最低位为 0 时，末尾有 t 个连续的 0 ，这 t 位之前有 m 个连续的 1 。把末尾的 t+m 的1 和倒数 t+m+1 的 0 对换，把倒数 t+1 到 t+m-1 的 1 移动到最低位
• 该二进制数的最低位为 1 时，末尾有 t 个连续的 0 ，把这 t 个连续的 1 和倒数第 t+1 位的 0 对换

这样就可以实现二进制数对应着每种 k 个数字的组合了

代码（C++）

递归

class Solution {
public:
    vector<vector<int>> nums;
    vector<int> ber;
    void dfs(int n, int k, int m) {
        if (n - m < k - 1)
            return ;
        if (k == 0) {
            nums.push_back(ber);
            return ;
        }
        for (int i = m; i <= n; ++ i) {
            ber.push_back(i);
            dfs(n, k - 1, i + 1);
            ber.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return nums;
    }
};

字典序

官方题解

class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;

    vector<vector<int>> combine(int n, int k) {
        // 初始化
        // 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]
        // 末尾加一位 n + 1 作为哨兵
        for (int i = 1; i <= k; ++i) {
            temp.push_back(i);
        }
        temp.push_back(n + 1);
        
        int j = 0;
        while (j < k) {
            ans.emplace_back(temp.begin(), temp.begin() + k);
            j = 0;
            // 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t
            // 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]
            while (j < k && temp[j] + 1 == temp[j + 1]) {
                temp[j] = j + 1;
                ++j;
            }
            // j 是第一个 temp[j] + 1 != temp[j + 1] 的位置
            ++temp[j];
        }
        return ans;
    }
};

总结

这题如果只说递归的方法那么算比较简单的，字典序法算比较难的。不过个人感觉掌握递归的方法就可以了，毕竟时间复杂度都是一样的，所以当然选择最简单的那个。这种组合之类的题还是很经典的，写多了就不会觉得难了。