Python neat 72ms. With recursive. Beat 99% (2016.11.15)

  • 0
    class Solution(object):
        def combinationSum(self, candidates, target):
            nums = sorted(list(set(candidates)))               # sort and remove the redundant numbers
            if not nums or nums[0]>target: return []         
            return self.comb(nums, target)
        def comb(self, nums, target):
            if not nums or nums[0]>target: return []       # no answer
            elif nums[0] == target: return [[target]]         # if the first of the num is the target: return it in a list
            # so the answer is made of 2 parts: 
            #  1. take the first elem and test the same group with the new target
            #  2. do not take the first one, test the same target from the rest of the nums
            return [[nums[0]]+elem for elem in self.comb(nums, target-nums[0])] + self.comb(nums[1:], target)

Log in to reply

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