爱华Fullstack

主题

爱华Fullstack2025-06-18
531
2.2m

组合 ​

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

示例 ​

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

题解 ​

javascript
/**
 * @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, 0, []);
    return target;
};

思路 ​

以示例中的值为例，可以认为是一个长度为 4的数组 [1, 2, 3, 4]，每两个组合一个数组可取 1组合其数组中之后的值，2与其数组中之后值，3与其数组中之后的值，4与其数组中之后值，即 [1, 2]、[1, 3]、[1, 4]、[2, 3]、[2, 4]、[3, 4]，首先初始条件判断，若是 n <= k则只能构成一个长度为 n的数组，将其装入二维数组返回即可，后边的表达式利用了 new Array(n)生成了一个长度为 n的空数组，让后取得其 keys的迭代器，利用 ...即 Spread操作符将其展开，之后使用 map将其处理为 key值 +1，之后定义目标数组，之后定义 dfs递归函数，首先进行剪枝，如果当前 tmp数组的大小为 s，未确定状态的区间 [cur,n]的长度为 t，如果 s + t < k，那么即使 t个都被选中，也不可能构造出一个长度为 k的序列，故这种情况就没有必要继续向下递归，之后判断递归深度如果与 k相等则直接将 tmp数组置入目标数组并返回，之后定义一个循环，从 cur开始到 n进行递归取值，将 tmp数组与 cur构建一个新数组传递到下一个递归中，之后启动递归初始化 cur为 1，深度 deep为 0，tmp为一个空数组，递归完成后返回目标数组即可。

每日一题 ​

https://github.com/WindrunnerMax/EveryDay

参考 ​

https://leetcode-cn.com/problems/combinations/
最近更新