回溯算法-leetcode#39-组合总和

class Solution {
public:
    vector<vector<int>> all;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    if(candidates.empty()) return all;
    vector<int> one;
    sort(candidates.begin(),candidates.end());
    com(candidates,target,one,0);
    return all;
    }
    void com(vector<int>& num,int target,vector<int> & one,int begin){
        if(target==0) {all.push_back(one); return;}
        for(int i=begin;i<num.size()&&num[i]<=target;i++)
        {
             if(num[i]<=target) 
             {
                 one.push_back(num[i]);
                 com(num,target-num[i],one,i);
             }
             one.pop_back();
        }
    }
};
           

自己写了一个，发现有重复序列，比如[2,3,6,7]中[2,2,3]和[2,3,2]不能重复出现，所以就是在递归的时候，限制下标大于等于刚刚使用过的下标i。当target目标是0时，说明one中序列匹配好了，直接加到最终结果all里面即可。奥对，提前排了个序，减少遍历次数。