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,且总和等于nif (res.si…...
JupyterLab使用指南(二):JupyterLab基础
第2章 JupyterLab基础 2.1 JupyterLab界面介绍 JupyterLab的用户界面非常直观和灵活。它包括文件浏览器、工作区、多标签页、命令面板和侧边栏等功能。以下是各个部分的详细介绍: 2.1.1 文件浏览器 文件浏览器位于界面左侧,用于导航和管理文件。你可…...
ubuntu18.04 + openssl + engine + pkcs11+ softhsm2 双向认证测试
安装环境 openssl 1.1.1 pkcs11-tool (由sudo apt-get install opensc 安装) libpksc11 (需源码安装apt install 只有libp11, 源码安装才有 libpksc11.so -> pkcs11.so) softhsm2 (由sudo apt-get install softhsm…...
【C++】类和对象2.0
俺来写笔记了,哈哈哈,浅浅介绍类和对象的知识点! 1.类的6个默认成员函数 俺们定义一个空类: class N {}; 似乎这个类N里面什么都没有,其实不是这样子的。这个空类有6个默认的成员函数 。 默认成员函数:…...
【LLM之KG】KoPA论文阅读笔记
研究背景 知识图谱补全(KGC)是通过预测知识图谱中缺失的三元组来完善知识图谱的信息。传统方法主要基于嵌入和预训练语言模型,但这些方法往往忽视了知识图谱的结构信息,导致预测效果不佳。 研究目标 本文的研究目标是探索如何将…...
UI设计速成课:理解模态窗口与非模态窗口的区别
我们日常所说的弹性框架是非常笼统的概念。我们习惯性地称之为对话框架、浮动层和提示条。弹性框架可以分为两种:模态弹性框架和非模态弹性框架。产品需要弹性框架来传递信息,用户需要弹性框架来接受反馈,但是没有经过推敲的弹出窗口设计很容易让用户感到…...
【Linux】基础IO_4
文章目录 六、基础I/O4. 动静态库 未完待续 六、基础I/O 4. 动静态库 既然我们能够成功创建静态库了,接下来我们将这个代码打包成动态库: shared: 表示生成共享库格式 fPIC:产生位置无关码(position independent code) 动态库库名规则&…...
C++模板类原理讲解
C模板类原理讲解 C模板是一种强大的编译期工具,它允许我们创建通用的、类型无关的类和函数。模板的主要目的是实现代码的重用和泛型编程。模板类的原理涉及以下几个方面: 模板的定义和实例化模板的类型参数模板特化模板的编译过程模板的优点和缺点 1.…...
scratch编程03-反弹球
这篇文章和上一篇文章《scratch3编程02-使用克隆来编写小游戏》类似(已经完全掌握了克隆的可以忽略这篇文章),两篇文章都使用到了克隆来编写一个小游戏,这篇文章与上篇文章不同的是,本体在进行克隆操作时,不…...
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劫持(HTTP Hijacking)是一种网络安全威胁,它发生在HTTP通信过程中,攻击者试图通过拦截、篡改或监控用户与服务器之间的数据流量,以达到窃取敏感信息或执行恶意操作的目的。今天我们就来详细了解HTTP劫持…...
System.Data.OracleClient.OracleException:“ORA-12571: TNS: 包写入程序失败
System.Data.OracleClient.OracleException:“ORA-12571: TNS: 包写入程序失败 解决方法: 首先%oracle_home%/network/admin下的sqlnet.ora文件,把SQLNET.AUTHENTICATION_SERVICES (NTS)加个 # 注释掉就好了...
saas产品运营案例 | 联盟营销计划如何帮助企业提高销售额?
在当今数字化时代,SaaS(软件即服务)产品已成为企业提高效率、降低成本的重要工具。然而,面对激烈的市场竞争,如何有效地推广SaaS产品、提高销售额,成为许多企业面临的挑战。林叔将以ClickFunnels为例&#…...
模式分解算法-满足3NF的无损且保持函数依赖的分解算法、满足BCNF的无损连接分解算法
一、引言 1、对指定的关系模式,若范式级别较低,为第一范式或第二范式,由于存在数据冗余或更新异常问题,在实际中一般是不可用的,关系模式的规范化就是将满足低一级的关系模式分解为若干满足高一级范式的关系模式的集合…...
荷兰与法国战平,双方能携手出现?
就在昨天晚上,荷兰队经历了90分钟的鏖战,最终0-0与法国队握手言和。此役,哈维-西蒙斯为荷兰队打进一球,但进球被判无效。从目前的积分形势来看,双方基本上确定携手晋级16强赛。本场比赛,荷兰队后卫内森-阿克…...
数据可视化实验二:回归分析、判别分析与聚类分析
目录 一、使用回归分析方法分析某病毒是否与温度呈线性关系 1.1 代码实现 1.2 线性回归结果 1.3 相关系数验证 二、使用判别分析方法预测某病毒在一定的温度下是否可以存活,分别使用三种判别方法,包括Fish判别、贝叶斯判别、LDA 2.1 数据集展示&am…...
FL论文专栏|设备异构、异步联邦
论文:Asynchronous Federated Optimization(12th Annual Workshop on Optimization for Machine Learning) 链接 实现Server的异步更新。每次Server广播全局Model的时候附带一个时间戳,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. 孤岛的总面积 | 代码随想录 代码:(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…...
根据状态转移写状态机-二段式
目录 描述 输入描述: 输出描述: 描述 题目描述: 如图所示为两种状态机中的一种,请根据状态转移图写出代码,状态转移线上的0/0等表示的意思是过程中data/flag的值。 要求: 1、 必须使用对应类型的状…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
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.构…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
