Recursive solution in python


  • 1
    B
    class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum(self, candidates, target):
        result=[]
        def recursivefind(result,sublist,cand,remain):
            if remain==0:
                result.append(sublist)
                return
            elif remain<0:
                return
            for i in cand:
                if len(sublist)>0 and i<sublist[len(sublist)-1]:
                    continue
                temp=sublist[:]
                temp.append(i)
                recursivefind(result,temp,cand,remain-i)
        recursivefind(result,[],candidates,target)
        
        return result
    

    the trick is to skip iterating elements in candidates if the element is smaller than what is already in the picked list


Log in to reply
 

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