leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

combination-sum.py (784B)

      1 class Solution:
      2     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
      3         searched = set()
      4         return make_combinations([], candidates, target, searched)
      5 
      6 
      7 def make_combinations(current, candidates, target, searched):
      8 
      9     current.sort()
     10 
     11     if str(current) in searched:
     12         return None
     13     else:
     14         searched.add(str(current))
     15 
     16     if sum(current) == target:
     17         return [current]
     18 
     19     if sum(current) > target:
     20         return None
     21 
     22     ret_ls = []
     23 
     24     for i in range(0, len(candidates)):
     25         copy_ls = current.copy()
     26         copy_ls.append(candidates[i])
     27         all_others = make_combinations(copy_ls, candidates, target, searched)
     28 
     29         if all_others is not None:
     30             ret_ls.extend(all_others)
     31 
     32     return ret_ls