Python DP & DFS Solution


  • 4

    DP Solution (Accepted, 60 ms):

    class Solution(object):
        def combinationSum4(self, nums, target):
            nums.sort()
            dp=[0]*(target+1)
            dp[0]=1 # if num == target
            for i in xrange(1,target+1):
                for num in nums:
                    if num>i:
                        break
                    dp[i]+=dp[i-num]
            return dp[target]
    

    DFS Solution (Time Limit Exceeded):

    DFS solution can only handle small cases(i.e.target<=25 && len(nums)<=5), due to large list memory usage of combs.

    class Solution(object):
        def combinationSum4(self, nums, target):
            nums.sort()
            path=[]
            combs=[]
            self.dfs(nums, target, path, combs)
            return len(combs)
        def dfs(self, nums, target, path, combs):
            if target==0:
                combs.append(path)
            for i in xrange(0,len(nums)):
                if nums[i]>target:
                    break
                self.dfs(nums, target-nums[i], path+[nums[i]], combs)

Log in to reply
 

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