Backtracking python solution


  • 0
    B
    class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum(self, candidates, target):
        if not candidates:
            return []
        candidates.sort()
        result=[]
        def backtracking(start,remaining,temp,result):
            if remaining<0:
                return
            if remaining==0:
                result.append(temp[:])
                return
            
            for i in range(start,len(candidates)):
                temp.append(candidates[i])
                backtracking(i,remaining-candidates[i],temp,result)
                temp.pop()
                
        backtracking(0,target,[],result)
        
        return result
    

    I am not sure if the DP version can possibly be faster.


Log in to reply
 

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