Sharing my 28ms C++ solution


  • 0
    T
    class Solution {
    private:
    void combinationSumHelper(vector<vector<int>>& result, vector<int>& candidates, int target, vector<int> temp, int sum,int j)
        {
            int n = candidates.size();
            if(sum == target)
            {
                result.push_back(temp);
                return;
            }
            else if(sum > target)
                return;
            else
            {
                vector<int> tempPlus = temp;
                int i;
                for(i=j; i<n; i++)
                {
                    if(sum+candidates[i]<=target)
                    {
                        tempPlus.push_back(candidates[i]);
                        combinationSumHelper(result, candidates, target, tempPlus, sum+candidates[i], i);
                        tempPlus.pop_back();
                    }
                }
            }   
        }
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<vector<int>> result;
            vector<int> temp;
            int sum=0;
            int j=0;
            combinationSumHelper(result, candidates, target, temp, sum, j);
            return result;
        }
    };

Log in to reply
 

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