Combination Sum

简介: Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

 

For example, given candidate set 2,3,6,7 and target 7
A solution set is: 
[7] 
[2, 2, 3] 

使用递归的方法实现:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        if(candidates.empty())
            return vector<vector<int> >();
        sort(candidates.begin(),candidates.end());
        vector<vector<int> > ret;
        vector<int> path;
        combination(candidates,0,target,ret,path);
        return ret;
    }

    void combination(vector<int> &candidates,int start,int target,vector<vector<int> > &ret,vector<int> &path)
    {
        if(target<0)
            return;
        if(target==0)
        {
            ret.push_back(path);
            return;
        }
        int i;
        for(i=start;i<(int)candidates.size();i++)
        {
            path.push_back(candidates[i]);
            combination(candidates,i,target-candidates[i],ret,path);
            path.pop_back();
        }
    }
};

int main()
{
    Solution s;
    vector<int> vec={2,3,6,7};
    vector<vector<int> > result=s.combinationSum(vec,7);
    for(auto a:result)
    {
        for(auto v:a)
            cout<<v<<" ";
        cout<<endl;
    }
}

运行结果:

相关文章
|
JavaScript API
vue数据更新但不改变视图,解决办法?
开发过程中会碰到数据更新,但是视图并未改变的情况,情况如下
937 0
|
4天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
3天前
|
云安全 人工智能 自然语言处理
阿里云x硅基流动:AI安全护栏助力构建可信模型生态
阿里云AI安全护栏:大模型的“智能过滤系统”。
|
3天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
4天前
|
Linux 虚拟化 iOS开发
VMware Workstation Pro 25H2 for Windows & Linux - 领先的免费桌面虚拟化软件
VMware Workstation Pro 25H2 for Windows & Linux - 领先的免费桌面虚拟化软件
939 4
VMware Workstation Pro 25H2 for Windows & Linux - 领先的免费桌面虚拟化软件
|
6天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
602 2