题解 | #加起来和为目标值的组合#

数组num中有重复元素，在回溯时需要进行剪枝和去重，剪枝部分为num[i]+sum<=target；去重的方法是if(i>index && num[i]==num[i-1]) continue;表示对于重复元素如果已经纵向遍历了，那么就不必再横向遍历了。

class Solution {
public:
    void backtrack(const vector<int>& num,int target,vector<vector<int>>& result,vector<int>& path,int index,int sum){
        if(sum==target){
            if(!count(result.begin(),result.end(),path))result.push_back(path);
            return;
        }
        for(int i=index;i<num.size() && num[i]+sum<=target;i++){
            if(i>index && num[i]==num[i-1]) continue;
            sum+=num[i];
            path.push_back(num[i]);
            backtrack(num, target, result, path, i+1,sum);
            path.pop_back();
            sum-=num[i];
        }
    }
    
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        vector<vector<int>> result{};
        vector<int> path{};
        backtrack(num, target, result, path, 0,0);
        return result;
    }
};