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

  • 1

    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
                prev = 0
                for i in range(m, len(nums)):
                    if target - sum < nums[i]:
                    if nums[i] == prev:     #record the previous visited candidates, can avoid duplicates at the first place 
                    prev = nums[i]
                    helper(result, path, nums, i + 1, sum + nums[i], target)
            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.