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
Beats 100.0% of Python submissions (recursion)


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 earlyout 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.