专栏首页算法修养LeetCode 39. Combination Sum

LeetCode 39. Combination Sum

暴力搜索

struct Node
{
    vector<int> a;
    int sum;
    int index;
    Node(){}
    Node(int index,int sum,vector<int> a)
    {
        this->index = index;
        this->sum = sum;
        this->a = a;
    }
    
};

class Solution {
public:
    queue<Node> q;  
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<vector<int>> ans;
        for(int i=0;i<candidates.size();i++)
        {
            vector<int> a;
            a.push_back(candidates[i]);
            q.push(Node(i,candidates[i],a));
        }
        
        while(!q.empty())
        {
            Node term = q.front();
            q.pop();
            
            if(term.sum==target)
            {
                ans.push_back(term.a);
                continue;
            }
            
            for(int i=term.index;i<candidates.size();i++)
            {
                if(term.sum+candidates[i]>target)
                    continue;
                else if(term.sum+candidates[i]==target)
                {
                     vector<int> x = term.a;
                    x.push_back(candidates[i]);
                    ans.push_back(x);
                }
                else
                {
                    vector<int> x = term.a;
                    x.push_back(candidates[i]);
                    q.push(Node(i,term.sum+candidates[i],x));
                }
            }
        }
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 40. Combination Sum II

    ShenduCC
  • LeetCode 113 Path Sum II

    ShenduCC
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • LeetCode 40. Combination Sum II

    ShenduCC
  • Golang语言-并发支持

    Golang 运行时(runtime)管理了一种轻量级线程,被叫做 goroutine。创建数十万级的 goroutine 是没有问题的。范例: packag...

    李海彬
  • 维多利亚的秘密 golang入坑系列

    原文在gitbook,字字原创,版权没有,转载随意。 在写本文的前一天,2017维密在上海开始了。 为了纪念屌丝界的盛世,特为本节起名维多利亚的秘密。现在的社会...

    随机来个数
  • 面试Mybatis之类型处理器​(typeHandlers)

    无论是MyBatis在预处理语句(PreparedStatement)中设置一个参数时,还是从结果集中取出一个值时, 都会用类型处理器将获取的值以合适的方式转换...

    小土豆Yuki
  • 正则表达式30分钟入门教程

    30分钟内让你明白正则表达式是什么,并对它有一些基本的了解,让你可以在自己的程序或网页里使用它。

    林德熙
  • 正则表达式30分钟入门教程--deerchao

    原文地址:http://www.cnblogs.com/deerchao/archive/2006/08/24/zhengzhe30fengzhongjiaoc...

    Edison Zhou
  • 六百字搞懂lambda

    在学习lambda之前,我们先搞清楚什么是函数。我理解的函数就是输入一些东西经过一定的规则后输出。假如我们超时买苹果,苹果的单价是5元,则f(x) = 5x;其...

    Java旅途

扫码关注云+社区

领取腾讯云代金券