Python solution 62ms beats 100% by searching with memorization


  • 0
    L

    Use a dictionary to memorize computed solutions to reduce redundancy.
    I think the code below is not hard to understand so I only explain by comments.

    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            candidates.sort()
            dict={} # its value type is List[List[int]]
            return self.search(target,candidates,dict)
    
        def search(self,current,candidates,dict):
            if current in dict:  #  if combinations of this value have been computed, don't do it again
                return dict[current]
    
            new_combinations = []
            for candidate in candidates:
                if candidate>current:
                    break
                elif candidate==current:
                    new_combinations.append([current])
                elif candidate*2>current: 
                    continue
                   # because if ture, then current - candidate < candidate, means no combinations of current - candidate can meet the condition below: if candidate <= an_old_combination[0]:
                else:
                    old_combinations=self.search(current-candidate,candidates,dict)
                    for an_old_combination in old_combinations:
                        if candidate <= an_old_combination[0]: # to make the combinations unique by make the list ascending
                            new_combinations.append([candidate]+an_old_combination)
    
            dict[current]=new_combinations # memorize
            return dict[current]
    

Log in to reply
 

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