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

题解

题目特点：同一集合内的数组成一个组合。

这可能是组合中最简单的一种了，直接按照回溯的模板套：

1. 递归终止条件
2. for循环的startIndex（如果是同一集合内组成组合，则需要通过设置startIndex，backtracing(i+1)来控制组合不会重复出现）
3. 回溯核心思想，加入->递归->递归结束->复原

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  const res = []; // 用来存放最后的结果
  const temp = []; // 用来存放中间出现的结果
  // 回溯
  function backtracing(startIndex) {
    if(temp.length === k) {
      res.push([...temp]);// temp是引用，必须拷贝一份值
      return ;
    }
    for(let i=startIndex; i<=n-(k-temp.length)+1; i++) {
      temp.push(i);
      backtracing(i+1);
      temp.pop();
    }
  }
  backtracing(1);
  return res;
};