现在的位置: 首页 > 综合 > 正文

leetcode Combination Sum &Combination Sum II

2019年04月02日 ⁄ 综合 ⁄ 共 1461字 ⁄ 字号 评论关闭

Combination Sum 要求target 在给定范围内的所有拆分,我是使用递归求解,先对向量进行排序,这样方便取数,以保证添加数的递增性质。

void myf(vector<vector<int> > &res,vector<int> &candidates, vector<int>re,int target,int i){
    if (target==0) {res.push_back(re);return;}
    if(target<0)return ;
    int len=candidates.size();
    for(;i<len;i++){
    if(candidates[i]<=target){
                re.push_back(candidates[i]);
                myf(res,candidates ,re,target-candidates[i],i);
         }else break;
         re.pop_back();
    }
        
}
class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        int len=candidates.size();
        vector<vector<int> > res;
        vector<int >re;
        sort(candidates.begin(),candidates.end());
        myf(res,candidates ,re,target,0);
        return res;
    }
};

void myf(vector<vector<int> > &res,vector<int> &candidates, vector<int>re,int target,int i){

    if (target==0) {
        res.push_back(re);return;}
    if(target<0)return ;
    int len=candidates.size();
    for(;i<len;i++){
    if(candidates[i]<=target){
                re.push_back(candidates[i]);
                myf(res,candidates ,re,target-candidates[i],i+1);
         }else break;
         re.pop_back();
    while(i<len&&candidates[i+1]==candidates[i])i++;
    }
        

}

Combination Sum II 要求在上一题的基础上追加了每个数最多使用一次,其实这样将上一题代码稍加修改,就可以做到每个数只去一次,有个需要注意的问题是,相同的解可能会添加两次,因此对于相同的值,在每一轮递归使用时,要在所有相同值中,只使用第一个。

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        int len=num.size();
        vector<vector<int> > res;
        vector<int >re;
        sort(num.begin(),num.end());
        myf(res,num ,re,target,0);
        return res;
    }
};

抱歉!评论已关闭.