Clear Python Code with Explanation, Beats 93%, Hope It Helps


  • 1
    Y

    A simple way to implement is to compare every complete path with the the previous paths, which actually works, but not good enough.
    One way to improve is to record the previous value of candidate, if the new candidates's values equal to the recorded one, continue.
    Pay attention to the position that the variable 'prev' is declared. It can make sure that the for loop won't continue at the first place.

            def helper(result, path, nums, m, sum, target):
                if sum == target:
                    #if path not in result:   the simple way to implement, need to do search everytime
                    result.append(path[:])
                    return
                prev = 0
                for i in range(m, len(nums)):
                    if target - sum < nums[i]:
                        return
                    if nums[i] == prev:     #record the previous visited candidates, can avoid duplicates at the first place 
                        continue
                    path.append(nums[i])
                    prev = nums[i]
                    helper(result, path, nums, i + 1, sum + nums[i], target)
                    path.pop()
            result = []
            path = []
            candidates.sort()     # put the duplicate candidates together
            s = 0
            m = 0
            helper(result, path, candidates, m, s, target)
            return result
    

Log in to reply
 

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