Iterative C++ solution that avoids duplicates


  • 0
    N
    void combHelper(vector<int>& candidates, int target, vector<int> comb, vector<vector<int>>& results){   
        for(int candidate:candidates){
            vector<int> tmp = comb;
            if(target-candidate<0){
                return;
            }
            if(target-candidate==0){
                if(tmp.empty() || candidate>=tmp.back()){ //avoid duplicates
                    tmp.push_back(candidate);
                    results.push_back(tmp);
                }
                return;
            }
            if(tmp.empty() || candidate>=tmp.back()){ //avoid duplicates
                tmp.push_back(candidate);
                combHelper(candidates, target-candidate, tmp, results);
            }
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> comb;
        vector<vector<int>> results;
        sort(candidates.begin(), candidates.end());
        combHelper(candidates, target, comb, results);
        return results;
    }

  • 0
    X

    This doesn't look like iterative at all.


Log in to reply
 

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