Accepted recursive solution in Python


  • 3
    L

    The code recursively find all combinations. Let me know if you have any questions.

    class Solution:
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
        def combinationSum(self, candidates, target):
            ans=[]
            candidates.sort() 
            for ii,elem in enumerate(candidates):
                if target>elem:
                    subSet=self.combinationSum(candidates[ii:],target-elem) # need to update the candidates list to avoid dublicates
                    if subSet:
                        ans+=[[elem]+lis for lis in subSet]
                elif target==elem:
                    ans+=[[elem]]
                else:
                    break
            return ans

  • 1
    W

    Is that necessary to sort the candidates each time when the recursion function being called?


Log in to reply
 

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