My Python recursive solution. Quite fast, around 100 ms


  • 2
    B
    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)

  • 0
    L

    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

  • 0
    B

    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.


Log in to reply
 

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