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

191.回溯算法:组合总和|||(力扣)

代码解决

class Solution {
public:vector<vector<int>> result;  // 存储所有符合条件的组合vector<int> res;  // 当前组合// 回溯函数void backtracing(int k, int n, int index, int sum) {// 如果当前组合的长度等于k,且总和等于nif (res.size() == k && sum == n) {result.push_back(res);return;}// 如果当前组合的长度超过k,或总和超过n,剪枝返回if (res.size() > k || sum > n) {return;}// 从index开始遍历1到9的数字for (int i = index; i <= 9; ++i) {res.push_back(i);  // 将当前数字加入组合backtracing(k, n, i + 1, sum + i);  // 递归调用回溯函数res.pop_back();  // 回溯,移除最后一个加入的数字}}// 主函数vector<vector<int>> combinationSum3(int k, int n) {backtracing(k, n, 1, 0);  // 从1开始回溯return result;  // 返回所有符合条件的组合}
};

类和成员变量

  • class Solution: 定义了一个解决方案类。
  • vector<vector<int>> result: 用于存储所有满足条件的组合结果。每个组合都是一个整数数组。
  • vector<int> res: 用于存储当前的组合。随着回溯的进行,这个向量会不断变化。

方法:backtracing

  • 参数:

    • int k: 组合中数字的个数。
    • int n: 目标和。
    • int index: 当前选择数字的起始位置,防止重复选择。
    • int sum: 当前组合的数字和。
  • 逻辑:

    • 结束条件:
      • if (res.size() == k && sum == n): 当当前组合的长度等于k且总和等于n时,将当前组合添加到结果集中。
      • if (res.size() > k || sum > n): 当当前组合的长度超过k或总和超过n时,直接返回,不再进行后续计算,这是剪枝操作,减少不必要的计算。
    • 循环遍历:
      • for (int i = index; i <= 9; ++i): 遍历从index到9的数字。index确保了每次递归时不重复选择已经选择过的数字。
      • res.push_back(i): 将当前数字i添加到当前组合res中。
      • backtracing(k, n, i + 1, sum + i): 递归调用回溯函数,i + 1确保下一个数字从当前数字的下一个开始,sum + i更新当前组合的和。
      • res.pop_back(): 回溯时,将最后一个加入的数字移除,以便进行下一次组合。

方法:combinationSum3

  • 逻辑:
    • 调用backtracing(k, n, 1, 0)从数字1开始查找组合。
    • return result: 返回存储结果的result

回溯算法解释

回溯算法是一种系统地搜索问题解的算法,适用于满足特定条件的所有解。在这个问题中,回溯用于从数字1到9中选出k个数,使它们的和为n。每次递归调用都会在当前组合中添加一个新的数字,并继续尝试加入更多数字,直到满足条件或不满足条件而进行剪枝。通过回溯和剪枝,可以有效地找到所有满足条件的组合。

剪枝

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) {if (sum == targetSum) result.push_back(path);return; // 如果path.size() == k 但sum != targetSum 直接返回}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调整startIndexsum -= i; // 回溯path.pop_back(); // 回溯}}public:vector<vector<int>> combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear();   // 可以不加backtracking(n, k, 0, 1);return result;}
};

 

相关文章:

191.回溯算法:组合总和|||(力扣)

代码解决 class Solution { public:vector<vector<int>> result; // 存储所有符合条件的组合vector<int> res; // 当前组合// 回溯函数void backtracing(int k, int n, int index, int sum) {// 如果当前组合的长度等于k&#xff0c;且总和等于nif (res.si…...

JupyterLab使用指南(二):JupyterLab基础

第2章 JupyterLab基础 2.1 JupyterLab界面介绍 JupyterLab的用户界面非常直观和灵活。它包括文件浏览器、工作区、多标签页、命令面板和侧边栏等功能。以下是各个部分的详细介绍&#xff1a; 2.1.1 文件浏览器 文件浏览器位于界面左侧&#xff0c;用于导航和管理文件。你可…...

ubuntu18.04 + openssl + engine + pkcs11+ softhsm2 双向认证测试

安装环境 openssl 1.1.1 pkcs11-tool &#xff08;由sudo apt-get install opensc 安装&#xff09; libpksc11 &#xff08;需源码安装apt install 只有libp11, 源码安装才有 libpksc11.so -> pkcs11.so&#xff09; softhsm2 &#xff08;由sudo apt-get install softhsm…...

【C++】类和对象2.0

俺来写笔记了&#xff0c;哈哈哈&#xff0c;浅浅介绍类和对象的知识点&#xff01; 1.类的6个默认成员函数 俺们定义一个空类&#xff1a; class N {}; 似乎这个类N里面什么都没有&#xff0c;其实不是这样子的。这个空类有6个默认的成员函数 。 默认成员函数&#xff1a…...

【LLM之KG】KoPA论文阅读笔记

研究背景 知识图谱补全&#xff08;KGC&#xff09;是通过预测知识图谱中缺失的三元组来完善知识图谱的信息。传统方法主要基于嵌入和预训练语言模型&#xff0c;但这些方法往往忽视了知识图谱的结构信息&#xff0c;导致预测效果不佳。 研究目标 本文的研究目标是探索如何将…...

UI设计速成课:理解模态窗口与非模态窗口的区别

我们日常所说的弹性框架是非常笼统的概念。我们习惯性地称之为对话框架、浮动层和提示条。弹性框架可以分为两种:模态弹性框架和非模态弹性框架。产品需要弹性框架来传递信息&#xff0c;用户需要弹性框架来接受反馈&#xff0c;但是没有经过推敲的弹出窗口设计很容易让用户感到…...

【Linux】基础IO_4

文章目录 六、基础I/O4. 动静态库 未完待续 六、基础I/O 4. 动静态库 既然我们能够成功创建静态库了&#xff0c;接下来我们将这个代码打包成动态库&#xff1a; shared: 表示生成共享库格式 fPIC&#xff1a;产生位置无关码(position independent code) 动态库库名规则&…...

C++模板类原理讲解

C模板类原理讲解 C模板是一种强大的编译期工具&#xff0c;它允许我们创建通用的、类型无关的类和函数。模板的主要目的是实现代码的重用和泛型编程。模板类的原理涉及以下几个方面&#xff1a; 模板的定义和实例化模板的类型参数模板特化模板的编译过程模板的优点和缺点 1.…...

scratch编程03-反弹球

这篇文章和上一篇文章《scratch3编程02-使用克隆来编写小游戏》类似&#xff08;已经完全掌握了克隆的可以忽略这篇文章&#xff09;&#xff0c;两篇文章都使用到了克隆来编写一个小游戏&#xff0c;这篇文章与上篇文章不同的是&#xff0c;本体在进行克隆操作时&#xff0c;不…...

postgresql数据库进阶知识

postgresql数据库进阶知识 # 如果表存在就先删除 drop table if exists student; # 创建学生表 # id serial not null 表示id自增 # id integer not null 表示id不自增 create table student (id serial not nullconstraint student_pkprimary…...

关于HTTP劫持,该如何理解、防范和应对

一、引言 HTTP劫持&#xff08;HTTP Hijacking&#xff09;是一种网络安全威胁&#xff0c;它发生在HTTP通信过程中&#xff0c;攻击者试图通过拦截、篡改或监控用户与服务器之间的数据流量&#xff0c;以达到窃取敏感信息或执行恶意操作的目的。今天我们就来详细了解HTTP劫持…...

System.Data.OracleClient.OracleException:“ORA-12571: TNS: 包写入程序失败

System.Data.OracleClient.OracleException:“ORA-12571: TNS: 包写入程序失败 解决方法&#xff1a; 首先%oracle_home%/network/admin下的sqlnet.ora文件&#xff0c;把SQLNET.AUTHENTICATION_SERVICES (NTS)加个 # 注释掉就好了...

saas产品运营案例 | 联盟营销计划如何帮助企业提高销售额?

在当今数字化时代&#xff0c;SaaS&#xff08;软件即服务&#xff09;产品已成为企业提高效率、降低成本的重要工具。然而&#xff0c;面对激烈的市场竞争&#xff0c;如何有效地推广SaaS产品、提高销售额&#xff0c;成为许多企业面临的挑战。林叔将以ClickFunnels为例&#…...

模式分解算法-满足3NF的无损且保持函数依赖的分解算法、满足BCNF的无损连接分解算法

一、引言 1、对指定的关系模式&#xff0c;若范式级别较低&#xff0c;为第一范式或第二范式&#xff0c;由于存在数据冗余或更新异常问题&#xff0c;在实际中一般是不可用的&#xff0c;关系模式的规范化就是将满足低一级的关系模式分解为若干满足高一级范式的关系模式的集合…...

荷兰与法国战平,双方能携手出现?

就在昨天晚上&#xff0c;荷兰队经历了90分钟的鏖战&#xff0c;最终0-0与法国队握手言和。此役&#xff0c;哈维-西蒙斯为荷兰队打进一球&#xff0c;但进球被判无效。从目前的积分形势来看&#xff0c;双方基本上确定携手晋级16强赛。本场比赛&#xff0c;荷兰队后卫内森-阿克…...

数据可视化实验二:回归分析、判别分析与聚类分析

目录 一、使用回归分析方法分析某病毒是否与温度呈线性关系 1.1 代码实现 1.2 线性回归结果 1.3 相关系数验证 二、使用判别分析方法预测某病毒在一定的温度下是否可以存活&#xff0c;分别使用三种判别方法&#xff0c;包括Fish判别、贝叶斯判别、LDA 2.1 数据集展示&am…...

FL论文专栏|设备异构、异步联邦

论文&#xff1a;Asynchronous Federated Optimization&#xff08;12th Annual Workshop on Optimization for Machine Learning&#xff09; 链接 实现Server的异步更新。每次Server广播全局Model的时候附带一个时间戳&#xff0c;Client跑完之后上传将时间戳和Model同时带回…...

【Java毕业设计】基于JavaWeb的礼服租赁系统

文章目录 摘 要Abstract目录1 绪论1.1 课题背景和意义1.2 国内外研究现状1.2.1 国外研究现状 1.3 课题主要内容 2 开发相关技术介绍2.1 Spring Boot框架2.2 Vue框架2.3 MySQL数据库2.4 Redis数据库 3 系统分析3.1 需求分析3.1.1 用户需求分析3.1.2 功能需求分析 3.2 可行性分析…...

代码随想录训练营Day 66|卡码网101.孤岛的总面积、102.沉没孤岛、103.水流问题、104.建造最大岛屿

1.孤岛的总面积 101. 孤岛的总面积 | 代码随想录 代码&#xff1a;(bfs广搜) #include <iostream> #include <vector> #include <queue> using namespace std; int dir[4][2] {1,0,0,1,-1,0,0,-1}; int count; void bfs(vector<vector<int>>&a…...

根据状态转移写状态机-二段式

目录 描述 输入描述&#xff1a; 输出描述&#xff1a; 描述 题目描述&#xff1a; 如图所示为两种状态机中的一种&#xff0c;请根据状态转移图写出代码&#xff0c;状态转移线上的0/0等表示的意思是过程中data/flag的值。 要求&#xff1a; 1、 必须使用对应类型的状…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...