30 Days of Code [Day 12]

25 Aug 2021

QUESTION : 39. Combination Sum

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    void helper(vi &candidates, vector<vi>& res, vi v, int target, int n){
        if(target == 0){
            res.pb(v);
            return;
        }
        if(n == 0){
            return ;
        }
        if(candidates[n-1] <= target){
            v.pb(candidates[n-1]);
            helper(candidates, res, v, target-candidates[n-1], n);
            v.pop_back();
        }
        helper(candidates, res, v, target, n-1);
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vi> res;
        vi v;
        helper(candidates, res, v, target, candidates.size());
        return res;
    }
};

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    vector<vi> res;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vi v;
        calc(candidates, v, 0, 0, target);
        return res;
    }
    void calc(vi& a, vi& v, int idx, int sum, int target){
        if(sum == target){
            res.pb(v);
            return;
        }
        fo(i, idx, a.size()){
            if(sum + a[i] <= target){
                v.pb(a[i]);
                sum += a[i];
                calc(a, v, i, sum, target);
                sum -= a[i];
                v.pop_back();
            }
        }
    }
    
};