[77] 组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2

输出:

[

⁠ [2,4],

⁠ [3,4],

⁠ [2,3],

⁠ [1,2],

⁠ [1,3],

⁠ [1,4],

]

排列组合子集等一系列问题，由于没有可推导的规律，一般都是用最暴力的回溯法来解。

本题的注意点在，题目限制了子集的元素个数，因此在入栈 res 的时候需要判断一次 path 的长度。

function combine(n: number, k: number): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  backtrack(1);
  return res;

  function backtrack(start: number) {
    if (path.length === k) {
      res.push([...path]);
      return;
    }

    for (let i = start; i <= n; i++) {
      path.push(i);
      backtrack(i + 1);
      path.pop();
    }
  }
}