leetcode 40. 组合总和 II

利用set去重，一维vector判断相等需要都按照一种顺序排好
超时

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> can;
    set< vector<int> >ans;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        can = candidates;
        sort( can.begin(),can.end() );
        findw( {}, target,0);

        for( auto i:ans ){
            ret.push_back(i);
        }
        return ret;
    }

    void findw( vector<int> temp,int tar,int curpos ){
        //debug("____________")
        //debug( tar );
        //if( curpos < can.size()){
        //    debug( can[ curpos] )
        //}
        if(  tar == 0 ){

            ans.insert( temp );
            return;
        }else if( curpos >= can.size() || tar < 0 ){
            return;
        }

        temp.push_back( can[ curpos ] );
        findw( temp,tar - can[curpos],curpos+1 );
        temp.pop_back();

        findw( temp,tar, curpos+1 );

    }

};

剪枝，去重，具体的原理：
https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> can;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        can = candidates;
        sort( can.begin(),can.end() );
        findw( {}, target,0);

        return ret;
    }

    void findw( vector<int> temp,int tar,int curpos ){
        if(  tar == 0 ){
            ret.push_back( temp );
            return;
        }else if( curpos >= can.size() || tar < 0 ){
            return;
        }

        for( int i = curpos;i < can.size();i++){
            if( i == curpos || can[i] != can[i-1]){
                //if(curpos==0){
                //    debug(i)
                //}
                temp.push_back( can[ i ] );
                findw( temp,tar - can[i],i+1 );
                temp.pop_back();
                //findw( temp,tar, i+1 );
            }
        }
    }

};