077. 组合

题目描述:

难度：Middle

相关话题：回溯算法

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

示例:

输入:n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

---

思路：

这道题有一个特点就是每个数之和它后面的数组合，例如[1,2,3,4]，组合成4个数的，只存在[1,2,3,4],不会出现[3,2,1,4]之类的。

因此可以跟踪一个变量start，维护每次开始的索引位置，当长度打到k后，停止并且保存到结果。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  let res=[]
  function backtrack(start,arr){
    if(arr.length===k){
      return res.push(arr.slice())
    }
    for(let i=start;i<=n;i++){
      arr.push(i)
      backtrack(i+1,arr)
      arr.pop()
    }
  }
  backtrack(1,[])
  return res
};