Share my 12ms C++ backtracing solution.


  • 2
    A
    class Solution {
    public:
        vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
             vector<int> path;
             vector<vector<int> > ret;
             sort(candidates.begin(), candidates.end());
             search(candidates, 0, target, path, ret);
             return ret;
        }
        
        void search(vector<int> & candidates, int idx, int target, vector<int> & path, 
        vector<vector<int> > & ret)
        {
            if(target == 0)
            {
                ret.push_back(path);
                return;
            }
            if(idx == candidates.size() ||  target < candidates[idx])
                return;
            path.push_back(candidates[idx]);
            search(candidates, idx + 1, target - candidates[idx] , path, ret);
            path.pop_back();
            idx++;
            while(idx< candidates.size() && candidates[idx] == candidates[idx -1]) 
                idx++;
            search(candidates, idx, target , path, ret);
            
        }
    };

Log in to reply
 

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