# My Python recursive solution. Quite fast, around 100 ms

• ``````class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
sortedCandidates = sorted(candidates)
return self.__impl(sortedCandidates, target)

def __impl(self, sortedCandidatesSub, quota):
ret = list()
for i, c in enumerate(sortedCandidatesSub):
if quota > (c + c):
tails = self.__impl(sortedCandidatesSub[i:], quota - c)
ret += [[c]+l for l in tails]
elif quota == c + c:
ret.append([c, c])
elif quota == c:
ret.append([c])
elif quota < c:
break
return ret
``````

Ideas here are:

1. Sort the candidates and iterate in ascending order
2. Try to detect the only possibility ( c, 2 * c) as early as possible and return immediately
3. Adjust the order of if-then-else branches carefully
4. Try to do computing as less as possible
5. Try faster way. For instance, use c+c rather than c*2 (I am not sure whether this impact anything)

• Actually you do not need to use both c+c and c. Only the comparison with c is enough.

``````for i, c in enumerate(sortedCandidatesSub):
if quota > c:
tails = self.__impl(sortedCandidatesSub[i:], quota - c)
ret += [[c]+l for l in tails]
elif quota == c:
ret.append([c])
else:
break``````

• Yes, you are definitely right. In fact I had tried this one. It seems a little bit slower for it has one more recursive invocation.

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