C++ : Easy Recursion Solution


#1
void comb_sum(vector<vector<int>> &ans, vector<int> temp, int sum, int i, vector<int> &C, int t){

if(sum==t){
    if(!count(ans.begin(), ans.end(), temp))
        ans.push_back(temp);
    return;
}
else if(sum>t || i>=C.size()-1)
    return;

temp.push_back(C[i]);
comb_sum(ans, temp, sum+C[i], i, C, t);
temp.pop_back();
temp.push_back(C[i+1]);
comb_sum(ans, temp, sum+C[i+1], i+1, C, t);
temp.pop_back();
temp.pop_back();
temp.push_back(C[i+1]);
comb_sum(ans, temp, sum-C[i]+C[i+1], i+1, C, t);
   
return;

}

vector<vector > Solution::combinationSum(vector &A, int B) {

vector<vector<int>> ans;
sort(A.begin(), A.end());
vector<int> temp;
temp.push_back(A[0]);
comb_sum(ans, temp, A[0], 0, A, B);
return ans;

}

Time Complexity = O(3^B) because in worst case vector A may contain all 1 entries, so length of the longest path of the recursion tree will be = B.