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

题目

解法：先对原数组排序，利用树的深度遍历思想进行dfs，当target减为0时push到res中，去重的方法是在dfs过程中判断相邻数字是否相同if(i>index && num[i]==num[i-1])continue;如果前后数字相同则跳过

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<int>tmp;
        vector<vector<int>>res;
        sort(num.begin(),num.end());
        dfs(num,target,0,tmp,res);
        return res;
    }

    void dfs(vector<int> &num,int target,int index,vector<int>& tmp,vector<vector<int>>& res)
    {
        //target：剩余值  index：起始数组元素下标   tmp存放一组结果   res存放所有组合
        if(target<=0)
        {
            if(target==0)res.push_back(tmp);
            return;
        }
        for(int i=index;i<num.size();i++)
        {
            if(i>index && num[i]==num[i-1])continue;
            tmp.push_back(num[i]);
            dfs(num,target-num[i],i+1,tmp,res);//i+1从下一个元素开始
            tmp.pop_back();//去除最后一个元素
        }
        return;
    }
};