30 Days of Code [Day 13]

26 Aug 2021

QUESTION : 40. Combination Sum II

#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:
    set<vi> res;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vi v;
        sort(all(candidates));
        calc(candidates, v, 0, 0, target);
        if(candidates[candidates.size()-1] == target){
            vi tmp;
            tmp.pb(candidates[candidates.size()-1]);
            res.insert(tmp);
        }
        vector<vi> ans(all(res));
        return ans;
    }
    void calc(vi& a, vi& v, int idx, int sum, int target){
        if(target == sum){
            res.insert(v);
            return;
        }
        fo(i, idx, a.size()){
            if(i > idx && a[i]==a[i-1]) continue;
            if(sum + a[i] > target){
                break;
            }
            v.pb(a[i]);
            sum += a[i];
            calc(a, v, i+1, sum, target);
            sum -= a[i];
            v.pop_back();
            
        }
    }
};