组合

• https://leetcode.cn/problems/combinations/description/

描述

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

Typescript 版算法实现

1 ) 方案1: 递归实现组合型枚举

function combine(n: number, k: number): number[][] {
    const ans = [];
    const dfs = (cur, n, k, temp) => {
        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.length + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (temp.length == k) {
            ans.push(temp);
            return;
        }
        // 考虑选择当前位置
        dfs(cur + 1, n, k, [...temp, cur]);
        // 考虑不选择当前位置
        dfs(cur + 1, n, k, temp);
    }
    dfs(1, n, k, []);
    return ans;
};

2 ) 方案2: 非递归（字典序法）实现组合型枚举

function combine(n: number, k: number): number[][] {
    const temp = [];
    const ans = [];
    // 初始化
    // 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]
    // 末尾加一位 n + 1 作为哨兵
    for (let i = 1; i <= k; ++i) {
        temp.push(i);
    }
    temp.push(n + 1);

    let j = 0;
    while (j < k) {
        ans.push(temp.slice(0, 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;
};

3 ) 方案3：回溯一般思路

function combine(n: number, k: number): number[][] {
    const ret = []
    const path = [] //递归的时候用的临时，用来统计[2]

    function backtrack(n, k, i) {
        let len = path.length
        if (len === k) {
            ret.push([...path])
            return
        }
        // n=4，k=2  i = 1  len = 0
        // 1,2,3 选4，后面就没了
        for (let j = i; j <= n - k + len + 1; j++) {
            path.push(j)
            backtrack(n, k, j + 1)
            path.pop()
        }
    }

    backtrack(n, k, 1)
    return ret

    //   n=4 k=4
    //   root
    // 1,         2,    3, 4

    // 2,3,4,     3,4    [4]

    // 34
    // N叉树的遍历  剪枝
    // n = 4, k = 2
    //   root
    //   [1,2,3,4]
    // 1. 取1   [2,3,4]    
    //   取2     
    //   3
    //   4
    // 2. 2     [3,4]
    // 3  3     [4]
    // 4  4      []
};