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

LeetCode 40. Combination Sum II

题目

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;  
    map<int,int> m;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        
        sort(candidates.begin(),candidates.end());
        
        vector<vector<int>> ans;
        for(int i=0;i<candidates.size();i++)
        {
            if(m[candidates[i]]==0)
            {
                vector<int> a;
                  a.push_back(candidates[i]);
                 q.push(Node(i,candidates[i],a));
                m[candidates[i]]=1;
            }
        }
        
        while(!q.empty())
        {
            Node term = q.front();
            q.pop();
            
            if(term.sum==target)
            {
                ans.push_back(term.a);
                continue;
            }
            if(term.sum>target)
            {
                continue;
            }
            m.clear();
            for(int i=term.index+1;i<candidates.size();i++)
            {
                 if(m[candidates[i]]==1)
                    continue;
                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);
                    m[candidates[i]]=1;
                }
                else
                {
                    vector<int> x = term.a;
                    x.push_back(candidates[i]);
                    q.push(Node(i,term.sum+candidates[i],x));
                    m[candidates[i]]=1;
                }
            }
        }
        return ans;
    }
};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 39. Combination Sum

    ShenduCC
  • LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

    Given inorder and postorder traversal of a tree, construct the binary tree.

    ShenduCC
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • LeetCode 39. Combination Sum

    ShenduCC
  • Golang语言-并发支持

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

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

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

    随机来个数
  • 六百字搞懂lambda

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

    Java旅途
  • 扫雷游戏制作学习过程

    1. 扫雷游戏的构思:   设计为初级,中级,高级三个级别。      因此不妨设置为如下规格: 9x9 16x15和30x16 (行,列)规格不同地雷的数量也...

    Gxjun
  • 面试Mybatis之类型处理器​(typeHandlers)

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

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

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

    林德熙

扫码关注云+社区

领取腾讯云代金券