[回溯]组合总和

news/2025/2/14 4:06:00/

 

给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。
class Solution {
private:vector<vector<int>> result;vector<int> p;public:
int getsum()
{int sum=0;for(int i=0;i<p.size();i++){sum+=p[i];}return sum;
}void reslution(vector<int>& candidates, int target,int sum,int start) {if(getsum()>target)return ;if(sum==target){result.push_back(p);return;}for(int i=start;i<candidates.size();i++){p.push_back(candidates[i]);sum+=candidates[i];reslution(candidates,target,sum,i);sum-=candidates[i];p.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {reslution(candidates,target, 0, 0);return result;}
};


http://www.ppmy.cn/news/1362268.html

相关文章

数据结构-数组

一,数组基础及注意事项 1,用来储存一组相同的类型的数据. 2,在内存中,分配连续的空姐,数组创建时要指定容量(大小). 3,创建格式: 数据类型 []数组名 int[] arr new int[10] int[] arr2 {1,2,3,4}. 4,索引--访问数组时通过索引进行操作. (注意:一定要理解索引的含义,在数据结…

数据结构链表力扣例题AC(3)——代码以及思路记录

160. 相交链表 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 AC写法一 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//思…

深度学习基础(四)医疗影像分析实战

之前的章节我们初步介绍了卷积神经网络&#xff08;CNN&#xff09;和循环神经网络&#xff08;RNN&#xff09;&#xff1a; 深度学习基础&#xff08;三&#xff09;循环神经网络&#xff08;RNN&#xff09;-CSDN博客文章浏览阅读1.2k次&#xff0c;点赞17次&#xff0c;收…

中国象棋开源人工智能程序(带UI)搬运

我的老父亲一直想买一个人工智能象棋机器人陪他下棋&#xff0c;我就在Github上找了一个开源项目&#xff0c;带UI的中国象棋人工智能程序&#xff0c;其训练方法类似AlphaZero&#xff0c;因而叫Chinese Chess Zero (cczero)。虽然看起来很久没有维护了&#xff0c;但是棋力也…

LeetCode 2610.转换二维数组

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组&#xff1a; 二维数组应该 只 包含数组 nums 中的元素。 二维数组中的每一行都包含 不同 的整数。 二维数组的行数应尽可能 少 。 返回结果数组。如果存在多种答案&#xff0c;则返回其中任何一种。 请注意&…

美格智能联合罗德与施瓦茨完成5G RedCap模组SRM813Q验证,推动5G轻量化全面商用

全球5G发展进入下半场&#xff0c;5G RedCap以其低成本、低功耗的特性成为行业焦点。近日&#xff0c;中国移动携手合作伙伴率先完成全球最大规模、最全场景、最全产业的RedCap现网规模试验&#xff0c;推动首批芯片、终端具备商用条件&#xff0c;RedCap端到端产业已全面达到商…

高等数学(无穷小与无穷大)

目录 一、无穷小 二、无穷大 三、无穷小与无穷大的关系 四、无穷小量的阶的比较 一、无穷小 二、无穷大 三、无穷小与无穷大的关系 四、无穷小量的阶的比较

软件性能测试和功能测试有何联系和区别?第三方软件检测机构简析

软件性能测试和功能测试是软件开发过程中非常重要的两个环节。从根本上说&#xff0c;它们都是为了保证软件质量和可靠性&#xff0c;但它们的目标和方法却有所不同。 软件性能测试是评估软件在特定负载下的性能表现&#xff0c;包括响应时间、吞吐量、并发能力等指标。它通过…