Sharing my 16ms C++ solution


  • 0
    T
    class Solution {
    private:
        void backtracking(vector<int>& candidates, int target, int pos, vector<int>& temp, vector<vector<int>>& result)
        {
            int n = candidates.size();
            if(target==0)
                result.push_back(temp);
            if(pos>=n || target<=0)
                return;
            
            int nextPos = pos+1;
            while(nextPos<n && candidates[nextPos]==candidates[pos])
            {
                nextPos++;
            }
            
            int i, j;
            for(i=0; i<=nextPos-pos; i++)
            {
                if(target-i*candidates[pos]<0)
                    break;
                for(j=0; j<i; j++)
                    temp.push_back(candidates[pos]);
                backtracking(candidates, target-i*candidates[pos], nextPos, temp, result);
                for(j=0; j<i; j++)
                    temp.pop_back();
            }
        }
        
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<int> temp;
            vector<vector<int>> result;
            backtracking(candidates, target, 0, temp, result);
            
            return result;
        }
    };

Log in to reply
 

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