首页 > 代码库 > leetcode第一刷_Combination Sum Combination Sum II

leetcode第一刷_Combination Sum Combination Sum II

啊啊啊啊,好怀念这种用递归保存路径然后打印出来的题目啊,好久没遇到了。

分了两种,一种是可以重复使用数组中数字的,一种是每个数字只能用一次的。其实没有多大区别,第一种每次进入递归的时候都要从头开始尝试,第二种要找一个标记的数组,把已经用到过的排除掉,就像生成全排列时的做法一样。跟我一样用引用保存中间结果的话,要注意回退的情况。第二种回退时,要把用到的那个数也恢复为可用,就完全像全排列时做的一样。破例贴两个题的代码,因为他们是在是不值得用两片文章来写。

class Solution {
public:
    set<vector<int> > vis;
    bool used[1000];
    void getSum(vector<int> &num, vector<vector<int> > &res, vector<int> &tpres, int target){
        if(target == 0){
            vector<int> sortres = tpres;
            sort(sortres.begin(), sortres.end());
            if(vis.find(sortres) == vis.end()){
                vis.insert(sortres);
                res.push_back(sortres);
            }
            tpres.pop_back();
            return;
        }
        for(int i=0;i<num.size();i++){
            if(target<num[i])   continue;
            if(!used[i]){
                used[i] = 1;
                tpres.push_back(num[i]);
                getSum(num, res, tpres, target-num[i]);
                used[i] = 0;
            }
        }
        tpres.pop_back();
    }
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int> > res;
        if(num.size() <= 0) return res;
        vector<int> tpres;
        memset(used, 0, sizeof(used));
        getSum(num, res, tpres, target);
        return res;
    }
};

class Solution {
public:
	set<vector<int> > vis;
    void getSum(vector<int> &candidates, vector<vector<int> > &res, vector<int> &tpres, int target){
    	//cout<<target<<"*"<<endl;
        if(target<0){
            tpres.pop_back();
            return;
        }
        if(target == 0){
        	vector<int> sortres = tpres;
        	sort(sortres.begin(), sortres.end());
        	if(vis.find(sortres) == vis.end()){
	            res.push_back(sortres);
	            //for(int i=0;i<tpres.size();i++)
	            //	cout<<tpres[i]<<" ";
	            //cout<<endl;
	            vis.insert(sortres);
        	}
        	tpres.pop_back();
            return;
        }
        for(int i=0;i<candidates.size();i++){
        	if(target<candidates[i]) continue;
            tpres.push_back(candidates[i]);
            getSum(candidates, res, tpres, target-candidates[i]);
            //if(!tpres.empty())  tpres.pop_back();
        }
        if(!tpres.empty())  tpres.pop_back();
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > res;
        vector<int> tpres;
        if(candidates.size()<=0)    return res;
        getSum(candidates, res, tpres, target);
        return res;
    }
};