77. 组合(力扣LeetCode)

文章目录

  • 77. 组合
    • 题目描述
    • 回溯算法
    • 组合问题的剪枝操作

77. 组合

题目描述

给定两个整数 n 和 k,返回范围 [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

回溯算法

  • 对回溯算法不太了解的同学可以看这篇文章:回溯算法理论基础

  • 该题目的详细解析可以看这篇文章:第77题. 组合

看完这两篇文章后,可能有同学看懂了[12],[13],[14]组合中2,3,4是如何删除(回溯),但没看懂1是如何删除(回溯)的可以看下图:
在这里插入图片描述
代码如下:

// 定义解决方案类
class Solution {
public:
    // 组合的主要公共接口,返回所有可能的k个数的组合
    vector<vector<int>> combine(int n, int k) {
        // 从数字1开始进行回溯搜索
        backtracking(n, k, 1);
        // 返回搜索结果
        return result;
    }

private:
    // 用来存放最终的组合结果
    vector<vector<int>> result;
    // 用于在递归过程中存放当前的组合路径
    vector<int> path;

    // 回溯函数,递归生成所有可能的组合
    void backtracking(int n, int k, int startindex) {
        // 如果当前路径的长度等于k,说明找到了一个长度为k的组合
        if (path.size() == k) {
            // 将当前路径加入到结果集中
            result.push_back(path);
            // 返回上一层递归
            return;
        }
        // 从startindex开始,尝试所有可能的下一个元素
        for (int i = startindex; i <= n; i++) {
            // 将当前元素加入到当前路径
            path.push_back(i);
            // 递归调用backtracking,注意下一次递归开始的索引是i+1,这样就不会有重复的组合
            backtracking(n, k, i + 1);
            // 将当前元素从路径中移除,也称为回溯
            path.pop_back();
        }
        // 如果循环结束,返回上一层递归
        return;
    }
};

在这个代码中:

  • 类Solution包含一个公共成员函数combine,它初始化回溯过程并返回结果。
  • backtracking是一个递归函数,用于执行回溯搜索。它接受当前数字的范围n,组合的长度k,以及当前搜索的起始索引startindex。
  • 私有成员result用于存储最终的组合结果;path用于在递归过程中跟踪当前的组合路径。
  • 在backtracking函数中,通过循环遍历startindex到n的所有数字,并将每个数字添加到当前路径path中。每添加一个数字,就递归调用backtracking,直到达到组合的长度k。到达长度k时,将当前路径path添加到结果列表result中。
  • 在每次递归调用之后,path需要回溯,即移除最后一个元素,以便下一次递归调用可以尝试新的数字组合。

这种方法能够避免重复的组合,因为每次递归都从下一个数字开始,而不是从头开始。这样就保证了每个数字只使用一次,同时也保证了组合是按顺序生成的。

组合问题的剪枝操作

详细解析可以看这篇文章:77.组合优化
在这里插入图片描述
代码如下:

// 定义Solution类,这是一个解决方案类
class Solution {
public:
    // combine函数用于获取所有可能的组合
    vector<vector<int>> combine(int n, int k) {
        // 从数字1开始递归回溯搜索
        backtracking(n, k, 1);
        // 返回最终的结果列表
        return result;
    }

private:
    // result用于存储所有的组合
    vector<vector<int>> result;
    // path用于在递归中构建每个组合
    vector<int> path;

    // backtracking是核心的递归回溯函数
    void backtracking(int n, int k, int startindex) {
        // 如果当前路径中的数字数量已经达到k个,则将当前路径保存到结果列表中
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        // 进行循环,尝试所有可能的数
        // 注意:这里使用了优化,减少了搜索的范围,避免了不必要的递归
        // n - (k - path.size()) + 1是剪枝后的上界
        for (int i = startindex; i <= n - (k - path.size()) + 1; i++) {
            // 将当前数字i加入到当前组合路径中
            path.push_back(i);
            // 递归调用backtracking,进行下一层搜索,下一次搜索从i+1开始
            backtracking(n, k, i + 1);
            // 回溯,移除当前路径中的最后一个数字,回到上一步,尝试其它可能的数字
            path.pop_back();
        }
        // 当循环结束,返回上一层递归
        return;
    }
};

在这段代码中:

  • backtracking是一个递归函数,用于深入每一层搜索可能的组合。
  • path是一个临时向量,用于存储当前递归路径上的组合。
  • result是一个二维向量,用于存储所有有效的k个数的组合。
  • backtracking函数中的if语句是递归的终止条件,即当path的大小等于k时,将当前组合添加到结果中。
  • 循环中的i <= n - (k - path.size()) + 1是一个关键的优化,它保证了仅当还有足够的元素可供选择以填满剩余的位置时,循环才会继续。这样可以减少不必要的递归调用,提高算法的效率。

例如,如果n=4, k=2,并且目前path已经包含了一个元素(假设是1),则只需要在剩下的3个元素中选择一个(2, 3, 或4),而不需要再考虑选择1。如果当前path已经有两个元素,则循环不再进行,因为不需要更多元素。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/415647.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

搭建LNMP环境并配置个人博客系统

LNMP是Linux&#xff08;操作系统&#xff09;、Nginx&#xff08;Web服务器&#xff09;、MySQL&#xff08;数据库&#xff09;和PHP&#xff08;脚本解释器&#xff09;的组合&#xff0c;常用于部署高性能的动态网站&#xff0c;如WordPress等博客平台 一、安装Linux操作系…

运用ETL工具快速拉通“有成财务”

如何运用ETL工具拉取“有成财务”数据并保存到数据库&#xff1f; ETLCloud 是一个数据集成平台&#xff0c;它提供了实时数据处理、抽取、转换、加载以及变更数据捕获&#xff08;CDC&#xff09;等功能。这个平台致力于简化和自动化企业级的数据同步与传输任务&#xff0c;并…

如何恢复数据?5个实用数据恢复方法!

亲爱的朋友们&#xff0c;你是否也有过这样的经历&#xff0c;电脑里的数据突然消失&#xff0c;让你手足无措&#xff1f;别担心&#xff0c;今天我就来教你如何恢复数据&#xff0c;让你不再为数据丢失而烦恼。 首先&#xff0c;我们需要了解数据丢失的原因。可能是你不小心…

华为云磁盘挂载

华为云磁盘挂载 磁盘挂载情况 fdisk -l 2. 查看当前分区情况 df -h 3.给新硬盘添加新分区 fdisk /dev/vdb 4.分区完成&#xff0c;查询所有设备的文件系统类型 blkid 发现新分区并没有文件系统类型&#xff08;type为文件系统具体类型&#xff0c;有ext3,ext4,xfs,iso9660等…

基于偏微分方程离散化计算的地下换热器建模与温度检测matlab仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1地下换热器的建模 4.2温度检测技术 5.完整工程文件 1.课题概述 基于偏微分方程离散化计算的地下换热器建模与温度检测&#xff0c;模拟这个不锈钢圆桶中土壤的温度场和湿度场。 2.系统仿真结果 3.核…

五、数组——Java基础篇

五、数组 1、数组元素的遍历 1.1数组的遍历&#xff1a;将数组内的元素展现出来 1、普通for遍历&#xff1a;根据下表获取数组内的元素 2、增强for遍历&#xff1a; for&#xff08;数据元素类型 变量名&#xff1a;数组名&#xff09;{ 变量名&#xff1a;数组内的每一个值…

nginx之重写功能 模块指令 防盗链

一 重写功能 rewrite Nginx服务器利用 ngx_http_rewrite_module 模块解析和处理rewrite请求&#xff0c; 此功能依靠 PCRE(perl compatible regular expression)&#xff0c;因此编译之前要安装PCRE库&#xff0c;rewrite是 nginx服务器的重要功能之一&#xff0c;重写功…

网络:IPv6

1、由于IPv4地址资源枯竭&#xff0c;所以产生了IPV6。 版本长度地址数量IPv432 bit4 294 967 296IPv6128 bit340 282 366 920 938 463 374 607 431 768 211 456 2、IPv6的基本报头在IPv4报头基础上&#xff0c;增加了流标签域&#xff0c;去除了一些冗余字段&#xff0c;使报…

【Vue的单选按钮不选中已解决亲测】

伙计&#xff0c;你是否因为后台给vue前端已经传入了对应的单选按钮的数据&#xff0c;为啥还是不选中呢&#xff01;&#xff1f; 这个问题实话我百度乐很多都不能解决我的问题&#xff0c;最后机智如我的发现乐vue的自身的问题&#xff0c;后端返回的数据类型如果是数字int类…

算法day02_209.长度最小的子数组

推荐阅读 从零开始学数组&#xff1a;深入浅出&#xff0c;带你掌握核心要点 初探二分法 再探二分法 目录 推荐阅读209.长度最小的子数组题目思路解法暴力解法队列相加法&#xff08;滑动窗口&#xff09;对列相减法&#xff08;滑动窗口&#xff09; 系统的纪录一下刷算法的过…

[vscode] 1. 在编辑器的标签页下显示文件目录(标签页显示面包屑) 2. 在标题栏上显示当前文件的完整路径

1. 标签页显示面包屑 view->Appearance->Breadcrumbs 2. 在标题栏上显示当前文件的完整路径 搜索 window.title将原来的值activeEditorShort 修改为 activeEditorMedium 参考&#xff1a; vscode在编辑器的标签页下显示文件目录&#xff08;标签页显示面包屑&#xf…

ONLYOFFICE桌面编辑器v8.0完整指南:安装、特点与新增功能

文章目录 摘要引言安装主界面可填写的 PDF 表单双向文本支持电子表格中的新增功能其他改进与Moodle集成用密码保护PDF文件从“开始”菜单快速创建文档本地界面主题安装免费的 ONLYOFFICE桌面编辑器 总结 摘要 本文介绍了ONLYOFFICE桌面编辑器v8.0的安装、主界面特点以及新增功…

Python中检查一个数字是否是科技数的完整指南

目录 前言 什么是科技数&#xff1f; 如何判断一个数字是否是科技数&#xff1f; 分割数字并计算平方 Python实现科技数检测的示例代码 科技数的应用场景 1. 数字游戏 2. 数据处理 3. 算法优化 4. 数据结构设计 总结 前言 科技数&#xff08;Tech Number&#xff09;是一…

ABAP - OOALV 单击事件

OOALV的单击事件通过cl_gui_alv_grid内置事件hotspot_click实现,效果如下图显示实现步骤&#xff1a; 在Fieldcat中设置参数HOTSPOT参数&#xff0c;将列设置成热点。单击事件要和热点组合才能触发 gs_fieldcat-hotspot X. "热点 定义一个事件处理类及其操作处理 CLAS…

高性能图表组件LightningChart .NET v11.0发布——增强DPI感知能力

LightningChart完全由GPU加速&#xff0c;并且性能经过优化&#xff0c;可用于实时显示海量数据-超过10亿个数据点。 LightningChart包括广泛的2D&#xff0c;高级3D&#xff0c;Polar&#xff0c;Smith&#xff0c;3D饼/甜甜圈&#xff0c;地理地图和GIS图表以及适用于科学&am…

CSS3详解

1.什么是CSS css的优势 1、内容和表现分离 2、网页结构表现统一&#xff0c;可以实现复用 3、样式十分的丰富 4、建议使用独立于html的css文件 5、利用SE0,容易被搜索引擎收录&#xff01; CSS的几种导入方法 内部式 <style>h1{color: red;}</style> 外部式 嵌…

GL/gl.h: No such file or directory(CentOS8 QT5.12.12)

1.问题描述 新建的QT工程&#xff0c;出现如下问题&#xff1a; GL/gl.h: No such file or directory 2.原因分析 centos系统里面缺少opengl库 3.解决方法 运行命令&#xff1a; yum install mesa-libGL -devel -y

palworld-server-tool(0.5.7)使用指南

文章目录 说明管理工具&#xff08;docker版本&#xff09;部署教程使用指南RCON指令工具RCON使用广播内容右下角&#xff0c;有加入白明单&#xff0c;和封禁和踢出的功能 游戏中RCON命令使用 说明 本文&#xff0c;主要使简单的使用介绍&#xff08;其实也没有什么指导的&am…

代码遗产:探索祖传代码的历史、挑战与现代融合艺术

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua&#xff0c;在这里我会分享我的知识和经验。&#x…

【Prometheus】基于Altertmanager发送告警到多个接收方、监控各种服务、pushgateway

基于Altertmanager发送报警到多个接收方 一、配置alertmanager-发送告警到qq邮箱1.1、告警流程1.2、告警设置【1】邮箱配置【2】告警规则配置【3】 部署prometheus【4】部署service 二、配置alertmanager-发送告警到钉钉三、配置alertmanager-发送告警到企业微信3.1、注册企业微…