天天看點

[leetcode]Combination Sum II

class Solution {
public:
    void help(vector<int> &v,int now,int sum,int target,vector<int> &path,vector<vector<int> >&ans,bool last){
        //now表示目前的數
        //sum表示目前所選的數的和
        //target表示目标資料
        //path表示所有已選的數
        //last上一個數是否選擇
        //相同的數連續取,不能跳着取
        if(sum>target){
            return;
        }
        if(now>=v.size()){
            if(sum==target){//組合完成
                ans.push_back(path);
            }
            return;
        }
        if((now==)||(v[now-]!=v[now])||last){//第一個必須取;目前數和前一個數不一樣;目前數和前一個一樣,并且取了前一個數
            path.push_back(v[now]);
            help(v,now+,sum+v[now],target,path,ans,true);
            path.pop_back();//回複path
        }
        help(v,now+,sum,target,path,ans,false);//不取目前數
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());//排序
        vector<int> path;//已選的數
        vector<vector<int> > ans;//結果
        help(candidates,,,target,path,ans,true);
        return ans;
    }
};