C++算法练习-day54——39.组合总和
题目来源:. - 力扣(LeetCode)
题目思路分析
题目:给定一个整数数组 candidates 和一个目标数 target,找出所有独特的组合,这些组合中的数字之和等于 target。每个数字在每个组合中只能使用一次。
思路:
-
回溯法:回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解(或者至少不是最后一个解),回溯算法会通过在上一步进行一些变化来丢弃该解,即“回溯”并尝试另一个可能的候选解。
-
剪枝:在回溯过程中,如果当前组合的和已经超过了目标值
target,则可以提前终止当前路径的搜索,因为后续添加任何数字都会使总和更大。(题目中已说明candidates中的数都大于1)
代码:
#include <vector> class Solution {
public: // 回溯函数 void Backtracking(vector<vector<int>>& ans, vector<int>& pos, vector<int>& candidates, int target, int index, int& possum) { // 如果当前组合的和超过了目标值,直接返回 if (possum > target) { return; } // 如果当前组合的和等于目标值,将当前组合加入结果集 if (possum == target) { ans.push_back(pos); } // 遍历候选数组,从当前索引开始(因为每个数字只能使用一次) for (; index < candidates.size(); ++index) { // 选择当前数字 possum += candidates[index]; pos.push_back(candidates[index]); // 递归调用回溯函数,继续向下搜索 Backtracking(ans, pos, candidates, target, index + 1, possum); // 撤销选择,回溯 possum -= candidates[index]; pos.pop_back(); } } // 主函数,调用回溯函数 vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<int> pos; // 当前组合 vector<vector<int>> ans; // 结果集 int possum = 0; // 当前组合的和 // 调用回溯函数,从索引0开始搜索 Backtracking(ans, pos, candidates, target, 0, possum); return ans; }
};
知识点摘要
- 回溯法:一种通过递归和状态重置来构建所有可能解的算法。
- 剪枝:在搜索过程中提前终止不可能产生有效解的路径,以减少计算量。
- 状态重置:在回溯过程中,通过撤销选择来回到之前的状态,以便尝试其他可能的解。
通过这道题目,我们学习了如何使用回溯法来解决组合问题,并理解了剪枝和状态重置的重要性。回溯法是一种强大的算法,适用于解决许多组合和排列问题。在实际应用中,我们需要注意如何有效地进行剪枝,以减少不必要的计算,提高算法的效率。此外,对于涉及组合的问题,如果数组已排序,可以进一步简化问题,避免产生重复的组合。通过不断练习,我们可以更好地掌握回溯法的应用,提高解决复杂问题的能力。
相关文章:
C++算法练习-day54——39.组合总和
题目来源:. - 力扣(LeetCode) 题目思路分析 题目:给定一个整数数组 candidates 和一个目标数 target,找出所有独特的组合,这些组合中的数字之和等于 target。每个数字在每个组合中只能使用一次。 思路&a…...
计算机毕业设计PySpark+Hadoop中国城市交通分析与预测 Python交通预测 Python交通可视化 客流量预测 交通大数据 机器学习 深度学习
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
Linux的文件系统
这里写目录标题 一.文件系统的基本组成索引节点目录项文件数据的存储扇区三个存储区域 二.虚拟文件系统文件系统分类进程文件表读写过程 三.文件的存储连续空间存放方式缺点 非连续空间存放方式链表方式隐式链表缺点显示链接 索引数据库缺陷索引的方式优点:多级索引…...
【Vue3】从零开始创建一个VUE项目
【Vue3】从零开始创建一个VUE项目 手动创建VUE项目附录 package.json文件报错处理: Failed to get response from https://registry.npmjs.org/vue-cli-version-marker 相关链接: 【VUE3】【Naive UI】<NCard> 标签 【VUE3】【Naive UI】&…...
9)语法分析:半倒装和全倒装
在英语中,倒装是一种特殊的句子结构,其中主语和谓语(或助动词)的位置被颠倒。倒装分为部分倒装和全倒装两种类型,它们的主要区别在于倒装的程度和使用的场合。 1. 部分倒装 (Partial Inversion) 部分倒装是指将助动词…...
Scala关于成绩的常规操作
score.txt中的数据: 姓名,语文,数学,英语 张伟,87,92,88 李娜,90,85,95 王强,78,90,82 赵敏,92,8…...
使用Java实现度分秒坐标转十进制度的实践
目录 前言 一、度分秒的使用场景 1、表示方法 2、两者的转换方法 3、区别及使用场景 二、Java代码转换的实现 1、确定计算值的符号 2、数值的清洗 3、度分秒转换 4、转换实例 三、总结 前言 在地理信息系统(GIS)、导航、测绘等领域,…...
根据后台数据结构,构建搜索目录树
效果图: 数据源 const data [{"categoryidf": "761525000288210944","categoryids": "766314364226637824","menunamef": "经济运行","menunames": "经济运行总览","tempn…...
食品计算—FoodSAM: Any Food Segmentation
🌟🌟 欢迎来到我的技术小筑,一个专为技术探索者打造的交流空间。在这里,我们不仅分享代码的智慧,还探讨技术的深度与广度。无论您是资深开发者还是技术新手,这里都有一片属于您的天空。让我们在知识的海洋中…...
2411rust,1.83
原文 1.83.0稳定版 新的常能力 此版本包括几个说明在常环境中运行代码可干的活的大型扩展.这是指编译器在编译时必须计算的所有代码:常和静项的初值,数组长度,枚举判定值,常模板参数及可从(constfn)此类环境调用的函数. 引用静.当前,除了静项的初化器式外,禁止常环境引用静…...
tomcat加载三方包顺序
共享库 tomcat支持多个webapp共享一个三方库,而不需要每个webapp都引入该三方库 tomcat加载类顺序 bootstrap:加载jvm提供的类system:加载$CATALINA_HOME/bin下的bootstrap.jar,commons-daemon.jar,tomcat-juli.jar三个包//加载$CLASSPATH…...
计算机的错误计算(一百七十一)
摘要 探讨 MATLAB 中秦九韶(Horner)多项式的错误计算。 例1. 用秦九韶(Horner)算法计算(一百零七)例1中多项式 直接贴图吧: 这样,MATLAB 给出的仍然是错误结果,因为准…...
js对于json的序列化、反序列化有哪几种方法
在JavaScript中,对JSON(JavaScript Object Notation)进行序列化(将对象转换为JSON字符串)和反序列化(将JSON字符串转换为对象)是常见的操作。以下是一些常用的方法: 序列化…...
Linux——基础命令(2) 文件内容操作
目录 编辑 文件内容操作 1.Vim (1)移动光标 (2)复制 (3)剪切 (4)删除 (5)粘贴 (6)替换,撤销,查找 (7ÿ…...
简单搭建qiankun的主应用和子应用并且用Docker进行服务器部署
在node18环境下,用react18创建qiankun主应用和两个子应用,react路由用V6版本,都在/main路由下访问子应用,用Dockerfile部署到腾讯云CentOS7.6服务器的8000端口进行访问,且在部署过程中进行nginx配置以进行合理的路由访…...
Python知识分享第十六天
“”" 故事7: 小明把煎饼果子技术传给徒弟的同时, 不想把独创配方传给他, 我们就要加私有. 问: 既然不想让子类用, 为什么要加私有? 答: 私有的目的不是不让子类用, 而是不让子类直接用, 而必须通过特定的 途径或者方式才能使用. 大白话: ATM机为啥要设计那么繁琐, 直接…...
管家婆财贸ERP BR045.大类存货库存数量明细表
最低适用版本: C系列 23.8 插件简要功能说明: 库存数量明细表支持按存货展示数据更多细节描述见下方详细文档 插件操作视频: 进销存类定制插件--大类存货库存数量明细表 插件详细功能文档: 应用中心增加菜单【大类存货库存数…...
Pytorch-GPU版本离线安装
最近在复现一项深度学习的工作,发现自己的pytorch是装的cpu版的(好像当时是直接加清华源,默认是cpu版本)。从官网在线下载速度太慢,还时不时断开连接,我们可以配置conda的清华源去这个问题,但是考虑到是在用…...
k8s 1.28 二进制安装与部署
第一步 :配置Linux服务器 #借助梯子工具 192.168.196.100 1C8G kube-apiserver、kube-controller-manager、kube-scheduler、etcd、kubectl、haproxy、keepalived 192.168.196.101 1C8G kube-apiserver、kube-controller-manager、kube-scheduler、etcd、kubectl、…...
【C语言】扫雷游戏(一)
我们先设计一个简单的9*9棋盘并有10个雷的扫雷游戏。 1,可以用数组存放,如果有雷就用1表示,没雷就用0表示。 2,排查(2,5)这个坐标时,我们访问周围的⼀圈8个位置黄色统计周围雷的个数是1。排查(8,6)这个坐标时…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
