组合总和(力扣39)

这道题又在之前的基础上进行了变形。递归是在一个集合里进行,但每次递归我们可以选择重复的数字,这代表递归时不需要缩小集合范围。但是组合的无序性仍要考虑,所以每一层for循环的起始值还是需要用变量控制。另外,我们可以事先对元素排个序,因为此题需要求和并与目标值进行比较。通过排序,我们就可以进行剪枝操作,提高效率。大家可以结合我下面的代码及详细注释理解。

代码及详细注释如下:

class Solution {
public:
    //数组用来存放结果
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates,int target,int sum,int start){
        //剪枝
        if(sum > target){
            return;
        }
        //终止条件
          if(sum == target){ 
            result.push_back(path);
            return;
          }
          //用start控制for循环
          for(int i = start;i < candidates.size();i++){
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum,i);//递归
            //回溯
            sum -= candidates[i];
            path.pop_back();
          }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,0);
        return result;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/966171.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用Python实现PDF与SVG相互转换

目录 使用工具 使用Python将SVG转换为PDF 使用Python将SVG添加到现有PDF中 使用Python将PDF转换为SVG 使用Python将PDF的特定页面转换为SVG SVG&#xff08;可缩放矢量图形&#xff09;和PDF&#xff08;便携式文档格式&#xff09;是两种常见且广泛使用的文件格式。SVG是…

【大数据技术】搭建完全分布式高可用大数据集群(Kafka)

搭建完全分布式高可用大数据集群(Kafka) kafka_2.13-3.9.0.tgz注:请在阅读本篇文章前,将以上资源下载下来。 写在前面 本文主要介绍搭建完全分布式高可用集群 Kafka 的详细步骤。 注意: 统一约定将软件安装包存放于虚拟机的/software目录下,软件安装至/opt目录下。 安…

【C++篇】C++11新特性总结1

目录 1&#xff0c;C11的发展历史 2&#xff0c;列表初始化 2.1C98传统的{} 2.2&#xff0c;C11中的{} 2.3&#xff0c;C11中的std::initializer_list 3&#xff0c;右值引用和移动语义 3.1&#xff0c;左值和右值 3.2&#xff0c;左值引用和右值引用 3.3&#xff0c;…

Redis --- 使用HyperLogLog实现UV(访客量)

UV 和 PV 是网站或应用数据分析中的常用指标&#xff0c;用于衡量用户活跃度和页面访问量。 UV (Unique Visitor 独立访客)&#xff1a; 指的是在一定时间内访问过网站或应用的独立用户数量。通常根据用户的 IP 地址、Cookies 或用户 ID 等来唯一标识一个用户。示例&#xff1…

【机器学习案列】糖尿病风险可视化及预测

&#x1f9d1; 博主简介&#xff1a;曾任某智慧城市类企业算法总监&#xff0c;目前在美国市场的物流公司从事高级算法工程师一职&#xff0c;深耕人工智能领域&#xff0c;精通python数据挖掘、可视化、机器学习等&#xff0c;发表过AI相关的专利并多次在AI类比赛中获奖。CSDN…

单片机之基本元器件的工作原理

一、二极管 二极管的工作原理 二极管是一种由P型半导体和N型半导体结合形成的PN结器件&#xff0c;具有单向导电性。 1. PN结形成 P型半导体&#xff1a;掺入三价元素&#xff0c;形成空穴作为多数载流子。N型半导体&#xff1a;掺入五价元素&#xff0c;形成自由电子作为多…

llama.cpp GGUF 模型格式

llama.cpp GGUF 模型格式 1. Specification1.1. GGUF Naming Convention (命名规则)1.1.1. Validating Above Naming Convention 1.2. File Structure 2. Standardized key-value pairs2.1. General2.1.1. Required2.1.2. General metadata2.1.3. Source metadata 2.2. LLM2.2.…

Conmi的正确答案——Rider中添加icon作为exe的图标

C#版本&#xff1a;.net 8.0 Rider版本&#xff1a;#RD-243.22562.250&#xff08;非商业使用版&#xff09; 1、添加图标到解决方案下&#xff1a; 2、打开“App.xaml”配置文件&#xff0c;添加配置&#xff1a; <Applicationx:Class"ComTransmit.App"xmlns&q…

告别手动操作!用Ansible user模块高效管理 Linux账户

在企业运维环境中&#xff0c;服务器的用户管理是一项基础但非常重要的任务。比如&#xff0c;当有新员工加入时&#xff0c;我们需要在多台服务器上为他们创建账户并分配合适的权限。而当员工离职或岗位发生变化时&#xff0c;我们也需要迅速禁用或删除他们的账户&#xff0c;…

C++小等于的所有奇数和=最大奇数除2加1的平方。

缘由 三种思路解题&#xff1a;依据算术推导得到一个规律&#xff1a;小等于的所有奇数和等于最大奇数除以2加1的平方。将在后续发布&#xff0c;总计有十种推导出来的实现代码。 int a 0,aa 1,aaa 0;cin >> a; while (aa<a) aaa aa, aa 2;cout << aaa;i…

【CPP】CPP经典面试题

文章目录 引言1. C 基础1.1 C 中的 const 关键字1.2 C 中的 static 关键字 2. 内存管理2.1 C 中的 new 和 delete2.2 内存泄漏 3. 面向对象编程3.1 继承和多态3.2 多重继承 4. 模板和泛型编程4.1 函数模板4.2 类模板 5. STL 和标准库5.1 容器5.2 迭代器 6. 高级特性6.1 移动语义…

深入浅出谈VR(虚拟现实、VR镜头)

1、VR是什么鬼&#xff1f; 近两年VR这次词火遍网上网下&#xff0c;到底什么是VR&#xff1f;VR是“Virtual Reality”&#xff0c;中文名字是虚拟现实&#xff0c;是指采用计算机技术为核心的现代高科技手段生成一种虚拟环境&#xff0c;用户借助特殊的输入/输出设备&#x…

【Redis】安装配置Redis超详细教程 / Linux版

Linux安装配置Redis超详细教程 安装redis依赖安装redis启动redis停止redisredis.conf常见配置设置redis为后台启动修改redis监听地址设置工作目录修改密码监听的端口号数据库数量设置redis最大内存设置日志文件设置redis开机自动启动 学习视频&#xff1a;黑马程序员Redis入门到…

[LeetCode]day16 242.有效的字母异位词

242. 有效的字母异位词 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的 字母异位词 示例 1: 输入: s "anagram", t "nagaram" 输出: true示例 2: 输入: s "rat"…

[MoeCTF 2022]baby_file

题目 <html> <title>Heres a secret. Can you find it?</title> <?phpif(isset($_GET[file])){$file $_GET[file];include($file); }else{highlight_file(__FILE__); } ?> </html> 读取flag /?filephp://filter/readconvert.base64-encode…

Centos挂载镜像制作本地yum源,并补装图形界面

内网环境centos7.9安装图形页面内网环境制作本地yum源 上传镜像到服务器目录 创建目录并挂载镜像 #创建目录 cd /mnt/ mkdir iso#挂载 mount -o loop ./CentOS-7-x86_64-DVD-2009.iso ./iso #前面镜像所在目录&#xff0c;后面所挂载得目录#检查 [rootlocalhost mnt]# df -h…

判断您的Mac当前使用的是Zsh还是Bash:echo $SHELL、echo $0

要判断您的Mac当前使用的是Zsh还是Bash&#xff0c;可以使用以下方法&#xff1a; 查看默认Shell: 打开“终端”应用程序&#xff0c;然后输入以下命令&#xff1a; echo $SHELL这将显示当前默认使用的Shell。例如&#xff0c;如果输出是/bin/zsh&#xff0c;则说明您使用的是Z…

python 小游戏:扫雷

目录 1. 前言 2. 准备工作 3. 生成雷区 4. 鼠标点击扫雷 5. 胜利 or 失败 6. 游戏效果展示 7. 完整代码 1. 前言 本文使用 Pygame 实现的简化版扫雷游戏。 如上图所示&#xff0c;游戏包括基本的扫雷功能&#xff1a;生成雷区、左键点击扫雷、右键标记地雷、显示数字提示…

【重新认识C语言----文件管理篇】

目录 ​编辑 -----------------------------------------begin------------------------------------- 引言 1. 文件的基本概念 2. 文件指针 3. 文件的打开与关闭 3.1 打开文件 3.2 关闭文件 4. 文件的读写操作 4.1 读取文件 4.1.1 使用fgetc()读取文件 4.1.2 使用fg…

EasyExcel 导出合并层级单元格

EasyExcel 导出合并层级单元格 一、案例 案例一 1.相同订单号单元格进行合并 合并结果 案例二 1.相同订单号的单元格进行合并2.相同订单号的总数和总金额进行合并 合并结果 案例三 1.相同订单号的单元格进行合并2.相同订单号的商品分类进行合并3.相同订单号的总数和总金额…