My Python 92 ms solution


  • 0
    C

    Using recursion. See below for code:

    '''

    class Solution(object):
    def combinationSum(self, candidates, target):
    """
    :type candidates: List[int]
    :type target: int
    :rtype: List[List[int]]
    """

        ret = []
        candidates.sort()  # put in ascending order
      
        for i in range(len(candidates)):
            num, rlist, s = candidates[i], [], []
            if num < target:
                rlist = self.combinationSum(candidates[i:], target - num) # only count forward, not backward
                if rlist is not None:
                    for s in rlist:
                        s.append(num)
                        ret.append(s)
                continue
            elif num == target:
                rlist = [num]
                ret.append(rlist)
                continue
            else:  # i > target, break, given that candidates are in ascending order
                break
                
        return ret
    

    '''


Log in to reply
 

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