77. 组合(JS实现)

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

示例:

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

2 思路
这道题的思路主要深度优先构造一棵树,由于生成的组合无关顺序,因此每层循环的初始值都是父节点的值+1

3代码
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
if (k === 0) return [];

const result = [];

for (let i = 1; i <= n; i++) {
d([i], k – 1, i);
}

function d(arr, depth, begin) {
if (depth === 0) {
result.push(arr);
return;
}

for (let i = begin + 1; i <= n; i++) {
let temp = arr.slice();
temp.push(i);
d(temp, depth – 1, i);
}
}

return result;
};