首页 > 代码库 > [Leetcode]Combination Sum II

[Leetcode]Combination Sum II

//本题还是有点疑惑...

//和combination sum一样。dfs

//可是由于此时是不能够反复利用,可是假设存在两个1的话依照样例就能够反复用相同的数值,仅仅是不可多次使用

//Book上说用pre来推断。可是这样难道不会miss样例中的1,1,6的情况?...

//有或者dfs的函数就是依照各个subject出现次数而执行的...要想想...

class Solution {

public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        int len=num.size();
        vector<vector<int>> result;
        vector<int> temp;
        sort(num.begin(),num.end());
        dfs(num,target,0,temp,result);
        return result;
    }
    void dfs(vector<int>&num, int gap, int start, vector<int>&temp, vector<vector<int>>&result)
    {
        if(gap==0)
        {
            //if(result.find(temp)==result.end())//事实上说这么多就是这么个意思,但是明显vector<vector<int>>里面没有相应的find函数,编译报错
            result.push_back(temp);
            return;
        }
        int pre=-1;
        for(int i=start;i<num.size();i++){
            if(gap<num[i])continue;
            if(pre==num[i])continue;
            pre=num[i];
        temp.push_back(num[i]);
        dfs(num,gap-num[i],i+1,temp,result);
        temp.pop_back();
        }
    }
};

[Leetcode]Combination Sum II