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

【回溯】Leetcode 77. 组合【中等】

组合

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

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

示例 1:

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

解题思路

  • 定义递归函数:定义一个递归函数 backtrack 用来生成组合。
  • 递归终止条件:如果当前组合的长度达到 k,将其添加到结果列表中。
  • 选择元素:从当前起始元素到 n 进行迭代,选择每个元素加入当前组合。
  • 递归调用:选择元素后,递归调用函数生成下一个元素的组合。
  • 回溯:在递归完成后,移除当前选择的元素,尝试选择下一个元素。

Java实现

public class Combine {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<>();backtrack(1, n, k, new ArrayList<>(), res);return res;}private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> res) {// 如果组合完成if (path.size() == k) {res.add(new ArrayList<>(path));return;}// 从`start`到`n`遍历所有的数字for (int i = start; i <= n; i++) {// 将`i`添加到当前组合path.add(i);// 使用下一个整数完成组合backtrack(i + 1, n, k, path, res);// 回溯,通过移除`i`path.remove(path.size() - 1);}}// 测试用例public static void main(String[] args) {Combine solution = new Combine();System.out.println(solution.combine(4, 2)); // 期望输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]System.out.println(solution.combine(5, 3)); // 期望输出: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]}
}

时间空间复杂度

  • 时间复杂度:O(C(n, k) * k),其中 C(n, k) 是从 n 个数中选 k 个数的组合数。生成每个组合需要 O(k) 的时间。
  • 空间复杂度:O(k),递归栈的深度最多为 k,存储当前组合的路径 path 也需要 O(k) 的空间。

相关文章:

【回溯】Leetcode 77. 组合【中等】

组合 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1&#xff1a; 输入&#xff1a; n 4, k 2 输出&#xff1a; [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 解题思路 定义递归函数&#xff1…...

项目中常量的定义方式

方式一 在常量个数少的时候&#xff0c;通常情况下使用这种方式。 public class MqConstants {public static final String EXCHANGE_1 "exchange1";public static final String EXCHANGE_2 "exchange2";public static final String EXCHANGE_3 "…...

BL104钡铼多协议采集网关助力企业智能化转型

BL104钡铼多协议采集网关&#xff08;PLC物联网关BL104&#xff09;是为满足工业环境需求而设计的专业工业级协议转换网关。它在企业智能化转型过程中扮演着关键角色&#xff0c;为企业提供了高效、稳定的通信解决方案&#xff0c;助力企业实现智能化转型。 首先&#xff0c;P…...

【LC刷题】DAY08:151 55 28 459

【LC刷题】DAY08&#xff1a;151 55 28 459 文章目录 【LC刷题】DAY08&#xff1a;151 55 28 459151. 反转字符串中的单词 [link](https://leetcode.cn/problems/reverse-words-in-a-string/description/)55. 右旋字符串 [link](https://kamacoder.com/problempage.php?pid106…...

Debian 12.5 一键安装 Oracle 19C 单机

前言 Oracle 一键安装脚本&#xff0c;演示华为 Debian 12.5 一键安装 Oracle 19C 单机版过程&#xff08;全程无需人工干预&#xff09;。 ⭐️ 脚本下载地址&#xff1a;Shell脚本安装Oracle数据库 安装准备 1、安装好操作系统&#xff0c;建议安装图形化2、配置好网络3、上…...

ARP协议相关

把ip地址解析成mac地址这里的mac地址就是路由器的mac地址 免费ARP 源ip和目的ip都是一样的&#xff0c;那怎么让其他人更新arp表呢&#xff1f;&#xff1f; 是因为目标mac是全f&#xff0c;是一个广播报文 如果冲突就是ip一样但是mac又不一样 代理ARP pc1和pc4是在同一个子网…...

Github 2024-06-14 开源项目日报Top10

根据Github Trendings的统计,今日(2024-06-14统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量JavaScript项目2Python项目2非开发语言项目2TypeScript项目1Dart项目1Rust项目1Lua项目1Java项目1Jupyter Notebook项目1从零开始构建你喜爱的技…...

记录AE快捷键(持续补充中。。。)

记录AE快捷键 快捷键常用快捷键图层快捷键工具栏图层与属性常用指令视图菜单时间轴常规快捷键项目首选项功能摄像机操作 常用操作导入AI/PS工程文件加选一个关键参数快速回到上下一帧隐藏/显示图层关键帧拉长缩短关键帧按着鼠标左键不松手&#xff0c;在秒表那一列往下移动会都…...

基于springboot实现问卷调查系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现问卷调查系统演示 摘要 传统信息的管理大部分依赖于管理人员的手工登记与管理&#xff0c;然而&#xff0c;随着近些年信息技术的迅猛发展&#xff0c;让许多比较老套的信息管理模式进行了更新迭代&#xff0c;问卷信息因为其管理内容繁杂&#xff0c;管理数…...

React@16.x(29)useRef

目录 1&#xff0c;介绍2&#xff0c;和 React.createRef() 的区别3&#xff0c;计时器的问题 目前来说&#xff0c;因为函数组件每次触发更新时&#xff0c;都会重新运行。无法像类组件一样让一些内容保持不变。 所以才出现了各种 HOOK 函数&#xff1a;useState&#xff0c;u…...

无人机的力量——在民用方面的应用

无人机在民用方面的应用广泛且多样化&#xff0c;以下是对其应用的详细介绍&#xff1a; 影视航拍&#xff1a; 无人机航拍影像具有高清晰、大比例尺、小面积、高视角的优点&#xff0c;特别适合获取带状地区航拍影像&#xff08;如公路、铁路、河流、水库、海岸线等&#xff…...

探索档案未来,尽在ARCHE-2024

2024年第三届上海国际智慧档案展览会暨高峰论坛&#xff08;ARCHE-2024&#xff09;将于2024年6月19日至21日在上海跨国采购会展中心隆重举行。深圳市铨顺宏科技有限公司应邀参展&#xff0c;将以全新形象盛装亮相&#xff0c;展示其在档案管理领域的最新技术和解决方案。 ARC…...

Maven 核心插件 maven-clean-plugin 使用详解

在软件开发中&#xff0c;构建和管理项目的复杂性随着代码量和依赖的增加而不断提升。Maven作为一个强大的构建工具&#xff0c;简化了这一过程&#xff0c;并通过其插件机制提供了丰富的功能。其中&#xff0c;maven-clean-plugin 是Maven的核心插件之一&#xff0c;它在项目的…...

金融数据中心布线运维管理解决方案

金融行业的核心业务&#xff0c;如交易、支付、结算等&#xff0c;对网络的依赖程度极高。布线作为网络基础设施的重要组成部分&#xff0c;其稳定性和可靠性直接关系到业务的连续运行。因此&#xff0c;良好的布线管理能够确保网络系统的稳定运行&#xff0c;减少因网络故障导…...

C++初学者指南第一步---2. Hello world

C初学者指南第一步—2. Hello world 目录 C初学者指南第一步---2. Hello world1.源文件 “Hello.cpp”2.编译hello.cpp3.术语4.编译器标志5.不要使用 “using namespace std;” &#xff01; 1.源文件 “Hello.cpp” #include <iostream> // our first program int main…...

gitLab批量下载有权限的项目

前言 参考 https://www.jianshu.com/p/b3d4e5cee835 适用于git私服拉取个人所涉及权限的代码&#xff0c;方便有多个项目权限的人快速拉取自己所有权限的代码。 默认生成目录结构与gitlab一致 步骤一:获取权限你的代码权限文件d 从gitlab私服生成所有你有权限的代码信息 …...

解决 kali 中使用 vulhub 拉取不到镜像问题

由于默认情况下&#xff0c;访问的镜像是国外的&#xff0c;而从 2023 年开始&#xff0c;docker 的镜像网站就一直访问不了&#xff0c;所以我们可以把镜像地址改成国内的阿里云镜像地址。 1、在 cd /etc/docker/目录下创建或修改daemon.json文件 sudo touch daemon.json 2、在…...

CSS3 简介

CSS3 简介 CSS3&#xff0c;即层叠样式表的第三代&#xff0c;是网页设计和开发中不可或缺的技术之一。它为HTML元素提供了更加丰富和灵活的样式定义&#xff0c;使得网页不仅结构清晰&#xff0c;而且外观精美、交互性强。CSS3继承了CSS2的基本特性&#xff0c;并引入了许多新…...

springboot事务管理的机制是什么

SpringBoot的事务管理机制实质上是基于Spring框架的事务处理机制。其主要目的是确保一系列数据库操作要么全部成功&#xff0c;要么全部失败&#xff08;回滚&#xff09;&#xff0c;从而维护数据的完整性和一致性。 SpringBoot事务管理遵循ACID四大特性&#xff1a; 1、原子…...

Linux下tar命令解压缩

tar 命令是 Unix 和 Linux 系统中用来创建归档文件以及提取归档文件的工具。它通常用于备份文件或将多个文件和目录打包成一个单独的归档文件。默认情况下&#xff0c;tar 不会对文件进行压缩&#xff0c;但可以通过结合其他压缩工具&#xff08;如 gzip 或 bzip2&#xff09;来…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...