频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
[LeetCode] Combination Sum
2015-05-04 10:52:52         来源:康瑞部落  
收藏   我要投稿

 

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.

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]

解题思路:

这道题的题意是从n个正整数中选出值为特定值的所有元素,这n个数中每个数可以重复选用。

这是一个np难问题,暴力法。主要是通过回溯暴力。代码如下:

 

class Solution {
public:
    vector> combinationSum(vector& candidates, int target) {
        vector> result;
        int len=candidates.size();
        if(len==0){
            return result;
        }
        std:sort(candidates.begin(), candidates.end());
        map keyToNumber;  //相当于系数,表示每个数出现了多少次
        getResult(result, candidates, 0, keyToNumber, target);
    }
    
    void getResult(vector>& result, vector& uniqueCandidates, int candidateIndex, map& keyToNumber, int left){
        if(left<0){
            return;
        }
        if(left==0){
            vector item;
            for(map::iterator it=keyToNumber.begin(); it!=keyToNumber.end(); it++){
                int number=it->second;
                int key = it->first;
                for(int i=0; i=uniqueCandidates.size()){
            return;
        }
        int number=0;
        while(left>=0){
            if(number!=0)
                keyToNumber[uniqueCandidates[candidateIndex]]=number;
            getResult(result, uniqueCandidates, candidateIndex+1, keyToNumber, left);
            if(number!=0){
                keyToNumber.erase(uniqueCandidates[candidateIndex]);
            }
            left = left-uniqueCandidates[candidateIndex];
            number++;
        }
    }
};


 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:C++数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。(牛客剑指offer)
下一篇:C++中求数组连续子向量的最大和(牛客剑指offer)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站