组合

组合

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

示例

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

题解

/**
 * @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构建一个新数组传递到下一个递归中,之后启动递归初始化cur1,深度deep0tmp为一个空数组,递归完成后返回目标数组即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/combinations/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 子集 II

    在本质上是一个组合问题,以一个长度为4的数组[1, 2, 3, 4]组合2个值为例,每两个组合一个数组可取1组合其数组中之后的值,2与其数组中之后值,3与其数组...

    WindrunnerMax
  • 子集

    给定一组不含重复元素的整数数组nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。

    WindrunnerMax
  • 全排列

    整体思路是利用回溯的方式,在具体递归的过程中类似于一棵决策树,首先定义一个用于递归的函数,分别传递原数组的引用、暂存数组的引用、目标数组的引用、递归深度,如果递...

    WindrunnerMax
  • Yii2框架踩坑记录-数组数据渲染到后台页面带分页

    不得不说Yii框架还是一个非常高效的框架,Gii扩展能生成简单的CRUD操作,问题也就出在这里,我的数据不是直接从单独的表出来的,需要连查,需要递归操作

    沈唁
  • 数据类型和Json格式

    作者: 阮一峰 1. 前几天,我才知道有一种简化的数据交换格式,叫做yaml。 我翻了一遍它的文档,看懂的地方不多,但是有一句话令我茅塞顿开。 它说,从结构上看...

    wangxl
  • 5.1 一维数组

    C语言入门到精通
  • CVPR2020 | CentripetalNet:48.0% AP,通过获取高质量的关键点对来提升目标检测性能

    论文地址:https://arxiv.org/pdf/2003.09119.pdf

    AI算法修炼营
  • 精通Excel数组公式011:令人惊叹的SUMPRODUCT函数

    本文主要探讨什么时候使用SUMPRODUCT函数更有效,而什么时候应该使用SUMIFS函数代替SUMPRODUCT函数。

    fanjy
  • mybatis动态sql语句

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    多凡
  • docker学习6-docker-compose容器集群编排

    实际工作中我们部署一个应用,一般不仅仅只有一个容器,可能会涉及到多个,比如用到数据库,中间件MQ,web前端和后端服务,等多个容器。 我们如果一个个去启动应用,...

    上海-悠悠

扫码关注云+社区

领取腾讯云代金券