Simple c++ solution, one more line than Combination Sum


  • 1
    I
    vector<vector<int>> res;
    vector<int> cur;
    
    void help(int start, int target, vector<int>& nums) {
        if (target == 0) {
            res.push_back(cur);
        } else {
            for (int i = start; i < nums.size() && nums[i] <= target; i++) {
                if (i != start && nums[i] == nums[i - 1]) continue;    // The key line, which ensures us no duplicates
                cur.push_back(nums[i]);
                help(i + 1, target - nums[i], nums);
                cur.pop_back();
            }
        }
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        cur.clear();
        res.clear();
        sort(candidates.begin(), candidates.end());
        help(0, target, candidates);
        return res;
    }

  • 0
    T

    Python Solution. No extra space need beside results. >77%

    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        return self.combinationSum(candidates,target)
    
    def combinationSum(self, candidates, target):
        result=[]
        for idx in range(0,len(candidates)):
            if (idx>0) & (candidates[idx]==candidates[idx-1]):
                continue
            
            var = candidates[idx]
            newtgt = target-var
            if newtgt==0:
                result.append([var])
            elif ((idx+1)<len(candidates)) and (newtgt>=candidates[idx+1]):
                for lst in self.combinationSum(candidates[idx+1::], newtgt):
                    lst.insert(0,var)
                    result.append(lst)
                
        return result

Log in to reply
 

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