Very Simple | c++ | Backtracking


#1
void helper(vector<int>&a, int target, set<vector<int>>&out,vector<int>&temp, int idx){
    if(target==0){
        out.insert(temp);
        return;
    }
    for(int i=idx;i<a.size();i++){
        
        if(a[i] > target) return;
        if(a[i] <= target)
            temp.push_back(a[i]);
        helper(a,target-a[i],out,temp,i);
        temp.pop_back();
    }
}

vector<vector<int> > Solution::combinationSum(vector<int> &a, int target) {
    sort(a.begin(),a.end());
    int n = a.size();
    set<vector<int>>out;
    vector<int>temp;
    helper(a,target,out,temp,0);
    vector<vector<int>>res;
    for(auto o : out)
        res.push_back(o);
    return res;
}