当前位置: 首页 > 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、 必须使用对应类型的状…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

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

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

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

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

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

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...