组合

给定两个整数 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]]

示例3：

输入：s = “” 输出：0

提示：

• 1 <= n <= 20
• 1 <= k <= n

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combinations/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

剪枝递归回溯

思路：回溯函数传入n，k和选择的元素位置start，在每层递归中，从start开始循环到 n - (k - path.length) + 1的位置，将这些数加入path，然后start加1，继续递归函数进入下一个分支，完成调用之后回溯状态，当path的长度等于k的时候终止这层分支，加入结果中。

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const res = [];
    // path 分支中的组合，start 搜索的起点
    const dfs = (path, start) => {
        const len = path.length;
        if (len === k) {    //组合长度与k一致时，即找到符合要求的组合
            // 拷贝赋值，以免影响其他分支
            res.push([].concat(path));
            return;
        }
        // 遍历从 start开始 到 n - (k -len) + 1结束，后面情况已经无法组成满足情况的组合，剪掉对应分支 
        for (let i = start; i <= n - (k - len) + 1; i++) {
            path.push(i);
            dfs(path, i+1);   // 递归下一层
            path.pop(); // 回溯到上一步
        }
    }
    dfs([], 1);
    return res;
};

时间复杂度：O(C(n, k)*k)
空间复杂度：O(n)

字典序法（非递归）

字典序，就是按照字典中出现的先后顺序进行排序。
字典序算法用来解决这样一个问题：给定其中一种排列，求基于字典序的下一种排列。
n = 4, k = 2中

「对应的二进制数」一列包含了由 k 个 1 和 n - k 个 0 组成的所有二进制数，并且按照字典序排列。这给了我们一些启发，我们可以通过某种方法枚举，使得生成的序列是根据字典序递增的。我们可以考虑我们一个二进制数数字 x，它由 k 个 1 和 n - k 个 0 组成，如何找到它的字典序中的下一个数字 {next}(x)，这里分两种情况：

• 规则一：x 的最低位为 1，这种情况下，如果末尾由 t 个连续的 1，我们直接将倒数第 t 位的 1 和倒数第 t + 1 位的 0 替换，就可以得到 {next}(x)。如 0011→0101，0101→0110，1001→1010，1001111→1010111。
• 规则二：x 的最低位为 0，这种情况下，末尾有 t 个连续的 0，而这 t 个连续的 0 之前有 m 个连续的 1，我们可以将倒数第 t + m 位置的 1 和倒数第 t + m + 1 位的 0 对换，然后把倒数第 t + 1位到倒数第 t + m - 1 位的 1 移动到最低位。如 0110→1001，1010→1100，1011100→1100011

至此，我们可以写出一个朴素的程序，用一个长度为 n 的 0/1 数组来表示选择方案对应的二进制数，初始状态下最低的 k 位全部为 1，其余位置全部为 0，然后不断通过上述方案求 next，就可以构造出所有的方案。
如果不通过二进制数，可以演变成另一个方案：
假设一个方案从低到高的K个数，分别是 {a_0,_a_1,⋯,_ak−1}，从低位向高位，找到第一个 j，使得 aj + 1 ≠ aj+1
出现在a序列中的数字在二进制数中对应为1，表示被选中。
则 aj + 1 ≠ aj+1 意味着 aj 和 aj+1 对应的二进制位中间有0，即这两个1不连续。
把 aj 对应的 1 向高位推送，也就是 aj←aj + 1
对于i∈[0,j−1] 内所有的 ai 把值恢复成 i + 1，即对应这 j 个 1 被移动到了二进制数的最低 j 位。

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const temp = [];
    const res = [];
    // 初始化 k个数的temp序列
    for (let i = 1; i <= k; i++) {
        temp.push(i);
    }
    // 设置哨兵为 n+1，使得字典序不会比当前方案大，作为跳出循环的依据
    temp.push(n+1);
    let j = 0;
    // 当j = k 时，不存在 temp[j+1]，需跳出循环
    while (j < k) {
        res.push(temp.slice(0, k));
        j = 0;
        // 当 temp[j] + 1 ≠ temp[j+1] 时，将对应位置数字+1（即后移遍历后面的数字）开启下个分支遍历
        // 当 temp[j] + 1 === temp[j+1] 时，表示当前分支已遍历过，回溯到上一步
        // 另一种解释
        // 寻找第一个 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++;
        }
        temp[j]++;
    }
    return res;
};