力扣39.组合总数
文章目录
- 力扣39.组合总数
- 题目描述
- 方法1:深搜回溯
力扣39.组合总数
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。
示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2], target = 1
输出: []
提示:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
方法1:深搜回溯
- 每一次,我们尝试往组合中添加一个位于给定数组中的数,获得一个新的中间结果状态result
- 将添加元素后的组合结果和求和结果作为参数或全局变量进入下一次dfs的初始参数
- 在新的初始参数上,判断当前组合的总和是否等于目标target:
- 若等于target则作为其中一个结果添加到结果集,然后返回再继续深搜
- 若结果大于target直接返回再深搜
- 若结果小于target,则尝试将从当前位置开始的元素及后续元素循环添加到组合中,进行下一次dfs
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/int result[40],sum;int **results;dfs(int *candidates,int candidatesSize,int target,int index,int *returnSize,int * columnSizes,int size){int i;if(sum==target){results[(*returnSize)]=(int *)calloc(40,sizeof(int*));for(i=0;i<size;i++) results[(*returnSize)][i]=result[i]; columnSizes[(*returnSize)++]=size;}else if(sum<target){for(i=index;i<candidatesSize;i++){sum+=candidates[i];result[size]=candidates[i];dfs(candidates,candidatesSize,target,i,returnSize,columnSizes,size+1);sum-=candidates[i];}}else return;}
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){ //初始化工作results=(int **)calloc(200,sizeof(int*));*returnSize=0;sum=0;int * columnSizes=(int *)calloc(200,sizeof(int ));memset(result,0,sizeof(int)*40);//深搜开始dfs(candidates,candidatesSize,target,0,returnSize,columnSizes,0);*returnColumnSizes=columnSizes;return results;
}

相关文章:
力扣39.组合总数
文章目录力扣39.组合总数题目描述方法1:深搜回溯力扣39.组合总数 题目描述 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可…...
sql的case when用法详解
简单CASE WHEN函数: CASE SCORE WHEN A THEN 优 ELSE 不及格 END CASE SCORE WHEN B THEN 良 ELSE 不及格 END CASE SCORE WHEN C THEN 中 ELSE 不及格 END等同于,使用CASE WHEN条件表达式函数实现: CASE WHEN SCORE A THEN 优WHEN SCORE …...
AtCoder Grand Contest 061(题解)
A - Long Shuffle 这道题本质是一个找规律的题 既然是打表题,我们先暴力把他打出来 (盗一张图.jpg) 接下来就是在这张图中挖掘答案 我们可以明显的看到偶数行是有一些规律的 要么是相邻对的互换,要么不变 不变和互换的位置也有讲究,在二进制…...
生成系列论文:文本控制的3d点云生成 TextCraft(一):论文概览
TextCraft: Zero-Shot Generation of High-Fidelity and Diverse Shapes from Text 论文原文: https://arxiv.org/abs/2211.01427 论文的研究动机 DALL2已经在文本控制的图像生成上取得很好的效果,但是基于文本控制的3d点云生成的研究还不太成熟&#…...
IDEA常用插件
常用IDEA插件 Codota 插件下载地址:Codota AI Autocomplete for Java and JavaScript - IntelliJ IDEs Plugin | Marketplace IDEA的自动补全功能已经很强大了,但是这个插件的自动补全功能更加强大,这是一个基于AI技术,学习了大量…...
Spring的事务传播机制
多个事务方法相互调用时,事务如何在这些方法之间进行传播,Spring中提供了七种不同的传播机制,来保证事务的正常执行: REQUIRED:默认的传播机制,如果存在事务,则支持/加入当前事务,如…...
Python:路径之谜(DFS剪枝)
题目描述 小张冒充 X 星球的骑士,进入了一个奇怪的城堡。 城堡里边什么都没有,只有方形石头铺成的地面。 假设城堡地面是 nn 个方格。如下图所示。 按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走…...
阿里巴巴在开源压测工具 JMeter 上的实践和优化
Apache JMeter [1] 是 Apach 旗下的开源压测工具,创建于 1999 年初,迄今已有超过 20 年历史。JMeter 功能丰富,社区(用户群体)庞大,是主流开源压测工具之一。 性能测试通常集中在新系统上线或大型活动前&…...
React Draggable插件实现拖拽功能
React Draggable插件实现拖拽功能1.下载Draggable插件2.引入Draggable插件3.设置一个div,并设置样式,并用Draggable包裹起来4.设置拖拽的范围5.Draggable常用props1.下载Draggable插件 npm install react-draggable2.引入Draggable插件 // 引入拖拽插件…...
MySQL-运算符
算术运算符: 加法运算-: 减法运算*: 乘法运算/: 除法运算,返回商%: 求余运算,返回余数例:创建n5表,插入数字100,查看数据表分别查看、-、*、/、%mysql> create table n5(-> num int); Query OK, 0 rows affected…...
Hudi-基本概念(时间轴、文件布局、索引、表类型、查询类型、数据写、数据读、Compaction)
文章目录基本概念时间轴(TimeLine)文件布局(File Layout)Hudi表的文件结构Hudi存储的两个部分Hudi的具体文件说明索引(Index)原理索引选项全局索引与非全局索引索引的选择策略对事实表的延迟更新对事件表的去重对维度表的随机更删…...
数据分享|中国各省、各市、各区县分年、分月、逐日平均气温数据(2000年~2019年)
今天分享给大家的是 2000 年~2019 年中国各省、各市、各县的分年、分月、逐日的平均气温数据(单位:摄氏度) 原始数据来源于国家气象科学数据共享服务平台-中国地面气候资料日值数据集(V3.0),原始数据是各个观测站点的日度数据,为了方便大家使用,我使用 Barnes 方法(…...
steam/csgo搬砖,2023年最暴利的项目
这个项目赚钱主要来源于两个地方: 1.比如说今天美元的汇率是1美元6.8人民币,那我们有特定的渠道能拿到1美元5.0-5.5左右人民币的价格,100美元的汇率差利润就有180元左右的利润,当然这个价格是根据国际的汇率上下会有浮动的。 2.…...
RDSDRDSPolarDBPolarDB-X的区别
RDS 阿里云关系型数据库(Relational Database Service,简称RDS),是一种稳定可靠、可弹性伸缩的在线数据库服务。 基于阿里云分布式文件系统和高性能存储,RDS支持MySQL、SQL Server、PostgreSQL和PPAS(Post…...
【Python学习笔记】30.Python3 命名空间和作用域
前言 本章介绍Python的命名空间和作用域。 命名空间 先看看官方文档的一段话: A namespace is a mapping from names to objects.Most namespaces are currently implemented as Python dictionaries。 命名空间(Namespace)是从名称到对象的映射,大…...
后量子 KEM 方案:Kyber
参考文献: Bos J, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM[C]//2018 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 2018: 353-367.Avanzi R, Bos J, Ducas L, et al. Crystals-kyber[J]. NIST…...
2019年广东工业大学腾讯杯新生程序设计竞赛(同步赛)
同步赛链接 A-原初的信纸(最值,STL) 题意: 找 n 个数的最大值. 参考代码: void solve() {int n;std::cin >> n;std::vector<int> a(n);for (auto &c : a)std::cin >> c;std::cout << *max_element…...
生产Nginx现大量TIME-WAIT,连接耗尽,该如何处理?
背景说明: 在尼恩读者50交流群中,是不是有小伙伴问: 尼恩,生产环境 Nginx 后端服务大量 TIME-WAIT , 该怎么办? 除了Nginx进程之外,还有其他的后端服务如: 尼恩,生产环境…...
Linux服务器clang-13安装(环境变量配置)
1.从llvm的github网址选择合适的release合适的运行平台进行下载,下载官方预编译的二进制压缩包。 2.将下载好的压缩包进行本地上传。 使用scp命令进行上传 scp -r -P 端口号 本地文件路径 服务器ID等:服务器上目标地址 3.解压(tar命令) 4.环境变量配…...
【C++】C/C++内存管理模板初阶
文章目录一、 C/C内存管理1. C/C内存分布2. C内存管理方式3. operator new与operator delete函数4. new和delete的实现原理5. 定位new表达式6. 常见面试题malloc/free和new/delete的区别内存泄漏二、模板初阶1. 泛型编程2. 函数模板3. 类模板一、 C/C内存管理 1. C/C内存分布 …...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
