My C++ Recursive Solution


  • 0
    M
    class Solution {
    public:
        vector<vector<int> > sol;
        void recursiveSearch (vector<int>& candidates, vector<int> oneSol, int target, int i) {
            if(target == 0) { sol.push_back(oneSol); return;}
            if(i == candidates.size()) return;
            if(target >= candidates[i]) {
                oneSol.push_back(candidates[i]);
                target -= candidates[i];
                recursiveSearch (candidates, oneSol, target,i+1);
            } else return;
            target += oneSol.back();
            oneSol.pop_back();
            i++; while(candidates[i] == candidates[i-1] && i < candidates.size()) i++;
            recursiveSearch (candidates, oneSol, target,i) ;
        }
        vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
            vector<int> oneSol;
            sort(candidates.begin(),candidates.end());
            recursiveSearch (candidates, oneSol, target, 0);
            return sol;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.