Concise recursive python solution


  • 0
    def combinationSum(self, candidates, target):
        if target==0: return [[]]
        ans = []
        for x in candidates:
            if x <= target:
                tmp = self.combinationSum(candidates, target-x)
                for l in tmp:
                    l.append(x)
                ans += tmp
        return [list(x) for x in set([tuple(sorted(l)) for l in ans])]
    

    The above solution is accepted by the OJ, but is slow. To optimize, sort candidate first, then use an index to avoid re-visiting the smaller candidates:

    def combinationSum(self, candidates, target):
        return self.combinationSum_helper(sorted(candidates), 0, target)
    
    def combinationSum_helper(self, candidates, i, target):
        if target==0: return [[]]
        ans = []
        for j in xrange(i,len(candidates)):
            x = candidates[j]
            if x > target: break
            tmp = self.combinationSum_helper(candidates, j , target-x)
            for l in tmp:
                l.insert(0,x)
            ans += tmp
        return ans

Log in to reply
 

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