当前位置: 首页 > news >正文

LeetCode-77-组合

在这里插入图片描述

一:题目描述:

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

你可以按 任何顺序 返回答案。

二:示例与提示

示例 1:

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

示例 2:

输入:n = 1, k = 1
输出:[[1]]

提示:

  • 1 <= n <= 20
  • 1 <= k <= n

三:思路

回溯+剪枝

对于这类组合问题,可以将题目所描述的数组通过组合去构建一个树形结构

image-20230908121855727

  • 横向拓展是数组中的元素个数,从1到n
  • 纵向拓展是深度,是对应元素的组合
  • 通过不断的递归和回溯,在每一层次中构建组合,搜索到对应的叶子节点
  • 图中每次搜索到了叶子节点,我们就找到了一个结果,将结果收集到结果集中即可

四:代码 + 复杂度分析

回溯+剪枝

/*** @param {number} n* @param {number} k* @return {number[][]}*/
var combine = function(n, k) {//回溯//确定回溯函数的参数//存放最终所有结果的数组const res = []//path单层结果const path = []const backtracking = (n, k, index) => {//终止条件if(path.length === k) {console.log(path)//收集结果res.push([...path])return }//单层逻辑for(let i = index; i <= n - (k - path.length) + 1; i++) {//路径收集path.push(i)//递归backtracking(n, k, i + 1)// console.log(path)//回溯path.pop()}}backtracking(n, k, 1)return res
};
  • 时间复杂度:O(C(n, k))

    • 对于每个数字,我们有两个选择(包括或不包括),并且我们有k个选择(需要选择k个数字)
    • 其中C(n, k)表示从n个元素中选择k个元素的组合数,也可以表示为二项式系数
  • 空间复杂度:O(k + 2^n)

    • 总的空间复杂度是 O(k + 2^n),其中 k 反映了递归树的深度,而 2^n 反映了结果数组 res 的可能长度

相关文章:

LeetCode-77-组合

一&#xff1a;题目描述&#xff1a; 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 二&#xff1a;示例与提示 示例 1: 输入&#xff1a;n 4, k 2 输出&#xff1a; [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4…...

Oracle中instr,rtrim,XMLPARSE,XMLAGG,GETCLOBVAL函数的使用

1&#xff1a;INSTR()函数 INSTR 是一个字符串函数&#xff0c;用于查找子字符串在源字符串中的位置。 它的语法如下&#xff1a; INSTR(source_string, search_string)source_string 是源字符串&#xff0c;即要在其中进行搜索的字符串。search_string 是要查找的子字符串。…...

java接入apiv3微信小程序支付(以java的eladmin框架为例)

一、需要准备的资料 1.小程序AppID 如&#xff1a;wx2e56f5****** 2.商户号 如&#xff1a;1641****** 3.商户API私钥路径&#xff1a;什么是商户API证书&#xff1f;如何获取商户API证书&#xff1f; 获取文件如下图&#xff1a; 如&#xff1a; 本地路径&#xff1a;E:\Env\e…...

第19节-PhotoShop基础课程-历史记录画笔工具

文章目录 前言1.历史记录画笔工具1.从当前状态创建文档2.创建新快照 2.历史记录艺术画笔工具 前言 任何记录都会被记录下来&#xff0c;并且可以拍快照&#xff0c;从历史中恢复&#xff0c;特别适合艺术创作的孩子 1.历史记录画笔工具 不只是画笔&#xff0c;所有操作记录都…...

MongoDB常用的比较符号和一些功能符号

比较符号 results collection.find({age: {$gt: 20}})功能符号 results collection.find({name: {$regex: ^M.*}})...

网络安全(黑客)技术自学

前言 一、什么是网络安全 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 无论网络、Web、移动、桌面、云等哪个领域&#xff0c;都有攻与防…...

C++ 引用

C 引用 引用变量是一个别名&#xff0c;也就是说&#xff0c;它是某个已存在变量的另一个名字。一旦把引用初始化为某个变量&#xff0c;就可以使用该引用名称或变量名称来指向变量。 C 引用 vs 指针 引用很容易与指针混淆&#xff0c;它们之间有三个主要的不同&#xff1a;…...

9.1.tensorRT高级(4)封装系列-自动驾驶案例项目self-driving-道路分割分析

目录 前言1. 道路分割总结 前言 杜老师推出的 tensorRT从零起步高性能部署 课程&#xff0c;之前有看过一遍&#xff0c;但是没有做笔记&#xff0c;很多东西也忘了。这次重新撸一遍&#xff0c;顺便记记笔记。 本次课程学习 tensorRT 高级-自动驾驶案例项目self-driving-道路分…...

稳定的 Glance 来了,安卓小部件有救了!

稳定的 Glance 来了&#xff0c;安卓小部件有救了&#xff01; 稳定版本的 Glance 终于发布了&#xff0c;来一起看看吧&#xff0c;看看这一路的旅程&#xff0c;看看好用么&#xff0c;再看看如何使用&#xff01; 前世今生 故事发生在两年的一天吧&#xff0c;其实夸张了…...

用友U8与MES系统API接口对接案例分析

企业数字化转型&#xff1a;轻易云数据集成平台助力 U8 ERPMES 系统集成 为什么选择数字化转型&#xff1f; 领导层对企业资源规划&#xff08;ERP&#xff09;的深刻理解促使了数字化转型的启动。采用精确的“N5”滚动计划&#xff0c;为供应商提供充分的预期信息&#xff0c…...

web UI自动化介绍

文章目录 一、web UI自动化介绍1.1 执行UI自动化测试前提1.2 Selenium介绍以及知识点梳理 二、Selenium 学习2.1 基础2.1.1 环境安装与基础使用2.1.2 web浏览器控制2.1.3 常见控件的八大定位方式2.1.3.1 八大定位方式介绍2.1.3.2 NAME、ID定位2.1.3.3 css_selector定位2.1.3.4 …...

小米13Pro/13Ultra刷面具ROOT后激活LSPosed框架微X模块详细教程

喜欢买小米手机&#xff0c;很多是因为小米手机的开放&#xff0c;支持root权限&#xff0c;而ROOT对普通用户来说更多的是刷入DIY模块功能&#xff0c;今天ROM乐园小编就教大家如何使用面具ROOT&#xff0c;实现大家日常情况下非常依赖的微X模块功能&#xff0c;体验微X模块的…...

文盘Rust -- 给程序加个日志 | 京东云技术团队

日志是应用程序的重要组成部分。无论是服务端程序还是客户端程序都需要日志做为错误输出或者业务记录。在这篇文章中&#xff0c;我们结合log4rs聊聊rust 程序中如何使用日志。 log4rs类似java生态中的log4j,使用方式也很相似 log4rs中的基本概念 log4rs 的功能组件也由 appe…...

C语言深入理解指针(非常详细)(五)

目录 回调函数qsort使用举例qsort函数的模拟实现sizeof和strlen的对比sizeofstrlensizeof和strlen的对比一道关于sizeof的题 回调函数 回调函数就是一个通过函数指针调用的函数 如果你把函数的指针&#xff08;地址&#xff09;作为参数传递给另一个函数&#xff0c;当这个指…...

[docker]笔记-portainer的安装

1、portainer是一款可视化的容器管理软件&#xff0c;利用portainer可以轻松方便的管理和创建容器。portainer本身是一个容器&#xff0c;完全免费并且具有汉化版。本文介绍portainer的安装和使用。 2、安装好容器并配置好容器环境&#xff0c;可参照https://blog.csdn.net/bl…...

详解TCP/IP的三次握手和四次挥手

文章目录 前言一、TCP/IP协议的三次握手1.1 三次握手流程 二、TCP/IP的四次挥手2.1 四次挥手流程 三、主要字段3.1、标志位&#xff08;Flags&#xff09;3.2、序号&#xff08;sequence number&#xff09;3.3、确认号&#xff08;acknowledgement number&#xff09; 四、状态…...

YOLOv5算法改进(16)— 增加小目标检测层

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。小目标检测层是指在目标检测任务中用于检测小尺寸目标的特定网络层。由于小目标具有较小的尺寸和低分辨率&#xff0c;它们往往更加难以检测和定位。YOLOv5算法的检测速度与精度较为平衡&#xff0c;但是对于小目标的检测效…...

蓝桥杯官网练习题(图像模糊)

题目描述 小蓝有一张黑白图像&#xff0c;由 nm 个像素组成&#xff0c;其中从上到下共 n 行&#xff0c;每行从左到右 &#xfffd;m 列。每个像素由一个 0 到 255 之间的灰度值表示。 现在&#xff0c;小蓝准备对图像进行模糊操作&#xff0c;操作的方法为&#xff1a; 对…...

使用鳄鱼指标和ADX开立空头的条件,3秒讲清楚

使用鳄鱼指标和ADX开立空头的条件其实很简单&#xff0c;anzo capital昂首资本3秒钟讲清楚。 首先&#xff0c;市场行情需呈水平状态。再者&#xff0c;均线体系开始向上发散&#xff0c;给出明确的信号。最后&#xff0c;ADX确认该信号&#xff0c;要求指数上涨20%以上&#…...

RabbitMQ死信队列与延迟队列

目录 死信队列 死信队列的定义 死信队列的应用场景 死信队列的作用 死信队列架构图 死信队列代码实现 延迟队列 延迟队列的定义 延迟队列的应用场景 延迟队列的作用 延迟队列架构图 延迟队列的代码实现 死信队列 死信队列的定义 死信队列&#xff08;Dead Letter …...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...