C++ 12ms O(nlog n) recursion solution. Just minor tweak from Combination Sum


  • 0
    W

    My solution for Combination Sum: https://leetcode.com/discuss/54545/c-20ms-o-nlog-n-recursion-solution

    The changes I made here are commented.

    void combinationSumHelper(vector<vector<int>>& result, vector<int>& candidates, 
                              int right, int target, vector<int>& partResult)
    {
        int upperBound = upper_bound(candidates.begin(), candidates.begin() + right, target) - candidates.begin() - 1;
        if (upperBound < 0) return;
        
        for (int i = upperBound; i >= 0; i--)
        {
            int newTarget = target - candidates.at(i);
            partResult.push_back(candidates.at(i));
            if (newTarget == 0)
            {
                result.push_back(partResult);
                partResult.pop_back();
    
                // skip duplicate number to prevent duplicate solution
                while (i > 0 && candidates.at(i) == candidates.at(i - 1)) 
                	i--;
                continue;
            }
    
            // i+1 is changed to i to only use a number once
            combinationSumHelper(result, candidates, i, newTarget, partResult);  
            partResult.pop_back();
    
            // skip duplicate number to prevent duplicate solution
            while (i > 0 && candidates.at(i) == candidates.at(i - 1))
            	i--;
        }
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
    {
        vector<vector<int>> result;
        if (candidates.empty()) return result;
        
        sort(candidates.begin(), candidates.end());
        
        vector<int> partResult;
        combinationSumHelper(result, candidates, candidates.size(), target, partResult);
        for (auto& r : result)
            reverse(r.begin(), r.end());
        return result;
    }

Log in to reply
 

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