题解 | 加起来和为目标值的组合(二)

#include <unordered_map>
class Solution {
public:
    //利用回溯的方法，进行凑数，每一层就是选与不选，
    //这里有重复问题，也就是：选过的数字是不能再一次选的，而正在选或从来没有选过的可以选，使用数组记录，同种数字选过都不能再选了，如果用哈希表不能做到正在使用也可以重复选
    vector<vector<int> > combinationSum2(vector<int>& num, int target) {
        vector< int >  temp;
        vector< vector<int> >  ans;

        sort(num.begin(), num.end());
        vector<int> mp(num.size(), 0);//初始化：0表示没有使用过；1表示正在使用；2表示使用过了；

        dp(target, 0, temp, ans, num, mp);

        return ans;
    }

    void dp(int target, int index, vector<int>& temp, vector< vector<int> >& ans, vector<int>& num, vector<int>& mp){
        if( target == 0 ){
            ans.push_back(temp);
            return;
        }

        if( target < 0 || index >= num.size() ){
            return;
        }

        //选
        if( index > 0 && (num[index] == num[index-1] && mp[index-1] == 2) ){  //从来都没选过，或者选了，可以再选； 但是不能选过了，再选
            mp[index] = 2;  //前面相同的数使用过了，这个数不能使用，同时标记让后面相同的数也不能使用
        }else{ //
            temp.push_back( num[index] );
            mp[ index ] = 1;

            dp(target-num[index], index+1, temp, ans, num, mp);

            temp.pop_back();
            mp[ index ] = 2;
        }
        
        //不选, 不用在意
        dp(target, index+1, temp, ans, num, mp);

        return;
    }
};