# Python solution 62ms beats 100% by searching with memorization

• 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]

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