组合
给定两个整数n@H_301_4@和k@H_301_4@，返回1 ... n@H_301_4@中所有可能的k@H_301_4@个数的组合。
示例
@H_301_14@输入: n = 4,k = 2
输出:
[
[2,4],[3,[2,3],[1,2],]
@H_301_4@
题解
@H_301_14@/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n,k) {
if(n <= k) return [[...new Array(n).keys()].map(v => v+1)];
var target = [];
var dfs = function(cur,deep,tmp){
if (tmp.length + (n - cur + 1) < k) return void 0;
if(deep === k){
target.push(tmp);
return void 0;
}
for(;cur<=n;++cur) dfs(cur+1,deep+1,[...tmp,cur]);
}
dfs(1,[]);
return target;
};
@H_301_4@
思路
以示例中的值为例，可以认为是一个长度为4@H_301_4@的数组[1,2,3,4]@H_301_4@，每两个组合一个数组可取1@H_301_4@组合其数组中之后的值，2@H_301_4@与其数组中之后值，3@H_301_4@与其数组中之后的值，4@H_301_4@与其数组中之后值，即[1,2]@H_301_4@、[1,3]@H_301_4@、[1,4]@H_301_4@、[2,3]@H_301_4@、[2,4]@H_301_4@、[3,4]@H_301_4@，首先初始条件判断，若是n <= k@H_301_4@则只能构成一个长度为n@H_301_4@的数组，将其装入二维数组返回即可，后边的表达式利用了new Array(n)@H_301_4@生成了一个长度为n@H_301_4@的空数组，让后取得其keys@H_301_4@的迭代器，利用...@H_301_4@即Spread@H_301_4@操作符将其展开，之后使用map@H_301_4@将其处理为key@H_301_4@值+1@H_301_4@，之后定义目标数组，之后定义dfs@H_301_4@递归函数，首先进行剪枝，如果当前tmp@H_301_4@数组的大小为s@H_301_4@，未确定状态的区间[cur,n]@H_301_4@的长度为t@H_301_4@，如果s + t < k@H_301_4@，那么即使t@H_301_4@个都被选中，也不可能构造出一个长度为k@H_301_4@的序列，故这种情况就没有必要继续向下递归，之后判断递归深度如果与k@H_301_4@相等则直接将tmp@H_301_4@数组置入目标数组并返回，之后定义一个循环，从cur@H_301_4@开始到n@H_301_4@进行递归取值，将tmp@H_301_4@数组与cur@H_301_4@构建一个新数组传递到下一个递归中，之后启动递归初始化cur@H_301_4@为1@H_301_4@，深度deep@H_301_4@为0@H_301_4@，tmp@H_301_4@为一个空数组，递归完成后返回目标数组即可。
每日一题
@H_301_14@https://github.com/WindrunnerMax/EveryDay
@H_301_4@
参考
@H_301_14@https://leetcode-cn.com/problems/combinations/
@H_301_4@