Share my accepted Python solution


  • 0
    F
    class Solution:
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
        def combinationSum(self, candidates, target):
            if len(candidates) == 0:
                return []
                
            # remove duplicate candidates from C
            candidates = sorted(set(candidates))
            
            out = []
            pool = [[]]
        
            # create the possible combinations from large number
            for i in candidates[::-1]:
                newpool = []
                for c in pool:
                    new = c
                    while True:
                        # insert new number into possible combinations
                        new = new + [i]
                        if sum(new) < target:
                            newpool.append(new)
                        elif sum(new) == target:
                            out.append(new[::-1])
                        else:
                            break
                pool += newpool 
            return out

Log in to reply
 

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