Beats 100.0% of Python submissions (recursion)


  • 1
    D
    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            candidates.sort()
            return self.helper(candidates, target)
            
        def helper(self, candidates, target):
            if target < candidates[0]:
                return []
            result = []
            for i in range(len(candidates)):
                c = candidates[i]
                if c < target:
                    partial = self.helper(candidates[i:], target - c)
                    if partial:
                        for l in partial:
                            l.append(c)
                            result.append(l)
                elif c == target:
                    result.append([c])
                else:
                    break
            return result
    

  • 0
    Y

    Awesome code! Can you give a bit explain where the improvement is?


  • 0
    D

    Thanks for your comment!
    I didn't check out the other Python solutions. I suspect this is fast because it sorts the candidates into increasing order and then has early-out logic to avoid iterating values that are too large to work (that's what the else: break is for). That order also avoids duplicate combinations, so no work required to suppress or eliminate them.


Log in to reply
 

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