128. 回溯算法

[goldEli]

随机给出两个正整数(n 和 k), 返回 1~n 中所有可能性的 k 个数组合，比如

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

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {

};

[goldEli]

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */

var combine = function(n, k) {
    var res = []

    function step(start, item) {
        if (item.length === k) {
            res.push([...item])
            return
        }
        for (let i = start; i < n+1; ++i) {
            // 加入第一个数
            item.push(i)
            // 加入第二个数
            step(i+1, item)
            // 回退
            item.pop()
        }
    }

    step(1, [])

    return res
};