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

力扣第216 组合总和 ||| c++ 回溯 + 注释

题目

216. 组合总和 III

中等

相关标签

数组   回溯

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

思路和解题方法

  1. backtracking() 方法中,首先进行终止条件的判断。如果当前组合的数字之和超过目标和 targetSum,直接返回。如果当前组合的大小等于 k,说明已经选取了足够数量的数字,如果当前组合的数字之和等于目标和,将当前组合加入到结果数组 result 中,并返回。
  2. 然后,使用一个循环从 startIndex9 - (k - path.size()) + 1 进行遍历。因为需要从 1~9 中选取数字,所以终止位置不可超过 9。根据题目要求,输入的 k,n 满足 1 ≤ k ≤ 9 且 1 ≤ n ≤ 45,因此最多只需要从 9-K+1 遍历到 9。
  3. 在循环内部,首先将当前数字加入到当前组合中,并将数字之和累加,然后通过递归调用 backtracking() 函数,在从 i+1 到 9 的范围内选择下一个数字。递归调用完成后,需要进行回溯操作,即将上一步加入组合的数字移出当前组合,并将数字之和减去该数字。这段代码同上一题的解法。
  4. 最后,在主函数 combinationSum3() 中,清空存储结果的数组 result 和存储组合的数组 path,并调用 backtracking() 方法开始生成所有符合条件的组合。最后返回所有符合条件的组合数组 result

复杂度

        时间复杂度:

                O(9^k)

时间复杂度:回溯算法的时间复杂度一般会被描述为指数级别,因为回溯问题一般有多个决策点和多个选择分支,例如本题中的组合问题就存在多个决策点(选取哪个数字)和多个选择分支(选取的数字不能重复且不能超过范围),因此它的时间复杂度在最坏情况下为 O(9^k),其中 k 表示组合的大小。需要注意的是,由于给定的 k 的范围为 1 ≤ k ≤ 9,因此实际运行效率比 O(9^k) 要好。

        空间复杂度

                O(k)

空间复杂度:回溯算法的空间复杂度也一般都很高,因为需要使用递归栈来保存状态和结果,例如本题中需要用递归栈来保存当前处理的数字、当前组合的大小、数字之和和结果集等信息,其空间复杂度也为指数级别,最坏情况下为 O(k),其中 k 表示组合的大小。

c++ 优化代码

class Solution {
private:vector<vector<int>> result; // 存放结果集vector<int> path; // 符合条件的结果// 回溯函数void backtracking(int targetSum, int k, int sum, int startIndex) {if (sum > targetSum) { // 剪枝操作return; }if (path.size() == k) { // 如果当前组合的大小等于 k,说明已经选取了足够数量的数字if (sum == targetSum) result.push_back(path); // 如果当前组合的数字之和等于目标和,将当前组合加入到结果数组中return; // 返回}for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 遍历可选的节点sum += i; // 处理节点,将当前的数字加入到当前组合中,并将数字之和累加path.push_back(i); // 处理节点,将当前的数字加入到当前组合中backtracking(targetSum, k, sum, i + 1); // 递归调用,从 i+1 到 9 的范围内选择下一个数字sum -= i; // 回溯,撤销处理的节点,将上一步加入的数字从数字之和中减去path.pop_back(); // 回溯,撤销处理的节点,将上一步加入的数字移出当前组合}}public:vector<vector<int>> combinationSum3(int k, int n) {result.clear(); // 可以不加,清空之前可能存在的结果集path.clear();   // 可以不加,清空之前可能存在的组合backtracking(n, k, 0, 1); // 从 1 开始进行回溯return result; // 返回符合条件的所有组合}
};

觉得有用的话可以点点赞,支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。

相关文章:

力扣第216 组合总和 ||| c++ 回溯 + 注释

题目 216. 组合总和 III 中等 相关标签 数组 回溯 找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次&#xff0c;组合可以以任何顺…...

深度学习系列51:hugging face加速库optimum

1. 普通模型 Optimum是huggingface transformers库的一个扩展包&#xff0c;用来提升模型在指定硬件上的训练和推理性能。Optimum支持多种硬件&#xff0c;不同硬件下的安卓方式如下&#xff1a; 如果是国内安装的话&#xff0c;记得加上-i https://pypi.tuna.tsinghua.edu.c…...

【QT开发笔记-基础篇】| 第四章 事件QEvent | 4.6 定时器事件

本章要实现的整体效果如下&#xff1a; QT 中使用定时器&#xff0c;有两种方式&#xff1a; 定时器类&#xff1a;QTimer定时器事件&#xff1a;QEvent::Timer&#xff0c;对应的子类是 QTimerEvent 本节通过一个案例&#xff0c;同时讲解这两种方式 案例&#xff1a;当点击…...

阿里云服务器ECS实例规格族c/g/r等字母说明

阿里云服务器ECS实例命名规则&#xff1a;ecs.<规格族>.large字母含义命名说明&#xff0c;包括x86、ARM架构、GPU异构计算、弹性裸金属、超级计算集群SCC云服务器&#xff0c;c代表计算型、g代表通用型、r代表内存型、u代表通用算力型、e代表经济型e实例&#xff0c;阿里…...

Everything和SVN结合使用-在Everything中显示SVN

点击跳转>Unity3D特效百例点击跳转>案例项目实战源码点击跳转>游戏脚本-辅助自动化点击跳转>Android控件全解手册点击跳转>Scratch编程案例点击跳转>软考全系列 &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分享&…...

代码随想录算法训练营第五十二天| 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

今日学习的文章链接和视频链接 123.买卖股票的最佳时机III 视频讲解&#xff1a;https://www.bilibili.com/video/BV1WG411K7AR https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html 188.买卖股票的…...

②. GPT错误:图片尺寸写入excel权限错误

꧂问题最初 ꧁ input输入图片路径 print图片尺寸 大小 长宽高 有颜色占比>0.001的按照大小排序将打印信息存储excel表格文件名 表格路径 图片大小 尺寸 颜色类型 占比信息input输入的是文件就处理文件 是文件夹&#x1f4c1;就处理文件。路径下的图片 1. 是处理本路径图片 …...

JQuery、JSON、AJAX、XML、IO流、多线程、反射核心知识点详解

JQuery 一、什么是JQuery JQuery是JavaScript的一个框架&#xff0c;对js的封装&#xff0c;使得js简单易学 优点&#xff1a; 1、不用考虑浏览器兼容性问题 2、jquery拥有强大的选择器&#xff0c;简化了js代码 3、jquery提供了很多系统函数&#xff0c;直接调用 二、版本 1.x…...

基于python的多种图像增强算法实现

基于python的多种图像增强算法实现 引言工具算法增强对比度直方图均衡化锐化图像噪声消除中值滤波均值滤波高斯滤波双边滤波增强对比度直方图均衡化总结全部资源引用引言 本项目使用python实现多种空域增强的图像增强算法,并使用了pyqt编写页面。通过点击不同页面的多种按钮,…...

Java前后端交互实现班级管理(查询)

1&#xff0c;数据库创建存储专业信息的表 2&#xff0c;后端&#xff1a; 连接数据库工具类DBUtil.java&#xff1a; package com.ffyc.webserver.util;import java.sql.*;public class DButils {static {try {Class.forName("com.mysql.cj.jdbc.Driver");} catch…...

论文速递 | 8月下旬9月上旬Operations ResearchManagement Science文章精选

编者按 本期我们选取了8月下旬及9月上旬Operations Research文章2篇&#xff0c;Management Science文章4篇期刊文章&#xff0c;着眼于各种不同场景下对于风险的预测、量化及管理&#xff0c;通过聚焦于风险这一主题&#xff0c;体系化地形成文章精选。 文章1 Computation of…...

DataBinding使用报错

val dataBinding DataBindingUtil.setContentView<ActivityMainBinding>(this,R.layout.activity_main)报错一&#xff1a; Unresolved reference: ActivityMainBinding 首先你要知道一个概念&#xff0c;ActivityMainBinding是DataBinding中的一种视频绑定&#xff…...

08Maven中的继承和聚合的作用

Maven中的继承 实际开发中对一个比较大型的项目进行了模块拆分 , 一个project下面创建了很多个modul, 每一个module都需要配置自己的依赖信息 开发中使用的同一个框架内的不同jar包&#xff0c;它们应该是同一个版本&#xff0c;所以整个项目中使用的框架版本需要统一 传统方…...

Ansible运行临时命令及常用模块介绍

目录 一.运行临时命令 1.基本语法格式 2.查看当前版本已安装的所有模块 二.ansible常见模块 1.command模块 2.shell模块 3.raw模块 4.script模块 5.file模块 参数列表&#xff1a; 示例&#xff1a; 6.copy模块 参数列表&#xff1a; 示例&#xff1a; 7.fetch模…...

EtherCAT报文-APRD(自动增量读)抓包分析

0.工具准备 1.EtherCAT主站 2.EtherCAT从站&#xff08;本文使用步进电机驱动器&#xff09; 3.Wireshark1.EtherCAT报文帧结构 EtherCAT使用标准的IEEE802.3 Ethernet帧结构&#xff0c;帧类型为0x88A4。EtherCAT数据包括2个字节的数据头和44-1498字节的数据。数据区由一个或…...

论文阅读:Seeing in Extra Darkness Using a Deep-Red Flash

论文阅读&#xff1a;Seeing in Extra Darkness Using a Deep-Red Flash 今天介绍的这篇文章是 2021 年 ICCV 的一篇 oral 文章&#xff0c;主要是为了解决极暗光下的成像问题&#xff0c;通过一个深红的闪光灯补光。实现了暗光下很好的成像效果&#xff0c;整篇文章基本没有任…...

将license验证加入到系统中

1.将ClientDemo下的cn文件夹的内容导入项目对应的java目录下。 2.将license-config.properties文件导入resources目录下。 3.在项目的pom.xml中添加如下依赖。 <properties><!-- Apache HttpClient --><httpclient>4.5.5</httpclient><!-- License…...

中断机制-interrupt和isInterrupted源码分析、中断协商案例

当前线程的中断标识为true&#xff0c;是不是线程就立刻停止&#xff1f; 答案是不立刻停止&#xff0c;具体来说&#xff0c;当对一个线程&#xff0c;调用interrupt时&#xff1a; 如果线程处于正常活动状态&#xff0c;那么会将该线程的中断标志设置为true&#xff0c;仅此…...

我与COSCon的故事【时光的故事】

曾经 2019年的时候&#xff0c;我还在日本读研究生&#xff0c;做一些物联网 (Internet of Things, IoT) 网络中的底层P2P (Peer to Peer) 通讯仿真模拟。这个方向是新来的Nguyen老师的新方向&#xff0c;它跟计算机强相关&#xff0c;但是很小众&#xff0c;实验室里也没有前辈…...

【科学文献计量】利用pybibx分析Scopus文献数据集(EDA,N-Grams,Cluster,Network analysis,NLP)

利用pybibx分析Scopus文献数据集 1 运行前准备1.1 数据集1.2 前置库2 加载库3 数据导入4 探索式数据分析,即EDA4.1 表格可视化4.2 词云图可视化4.3 N-Grams可视化4.4 文献聚类4.5 主题词演化4.6 桑基图可视化4.7 树图可视化4.8 作者生产力可视化5 网络可视化5.1 文献引用与被引…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...