9ms C++ backtracking solution Easy avoid duplication


  • 0
    S

    Easy understand solution. Use find() to avoid duplication

    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            vector<vector<int>> ans;
            vector<int> res;
            sort(candidates.begin(),candidates.end());
            myCombination(candidates,ans,res,target,0);
            return ans;
    }
        void myCombination(vector<int>& candidates, vector<vector<int>>& ans, vector<int>& res, int target, int begin)
        {
            if(target==0) {
                if(find(ans.begin(),ans.end(),res)!=ans.end()) return;
                ans.push_back(res); 
                return;}
            for(int i=begin;i<candidates.size();i++){
                if(candidates[i]>target) return;
                else{
                    res.push_back(candidates[i]);
                    myCombination(candidates,ans,res,target-candidates[i],i+1);
                    res.pop_back();
                }
            }
        }
    };
    

Log in to reply
 

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