Python simple DP, Backtracking and DFS (recursive) with memorization


  • 0
    J

    The problem is converted to a typical "subset sum" problem - looking for half of the sum of the input array.

    Here are three of the solutions ( should be all accepted.)

    1. DP solution with update rule:
      dp[i][j] = dp[i-1][j] if nums[i-1] > j, nums[i-1] can't be picked.
      dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]] if nums[i-1] <= j, it is okay to pick nums[i-1]
      Notice the sizes of matrix dp[N+1][S+1]
    class Solution(object):
        def canPartition(self, nums):
            s = sum(nums)
            if s & 1: return False
            s >>= 1
            n = len(nums)
            dp = [[0 for _ in range(s + 1)] for _ in range(n + 1)]
            for i in range (n + 1): dp[i][0] = 1
            for i in range (1, n + 1):
                for j in range(1, s+1):
                    if j < nums[i - 1]:
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i - 1]]
            return bool(dp[n][s])
    
    
    1. Backtracking with memorization:
        def canPartition(self, nums):
            nums.sort()
            s = sum(nums)
            if s % 2: return False
            s = s / 2
            return self.findSum(nums, 0, s, {})
    
        def findSum(self, nums, start, target, memo):
            if (start, target) in memo:
                return memo[(start, target)]
            if target < 0:
                return
            elif target == 0:
                return True
            for i in range(start, len(nums)):
                if self.findSum(nums, i + 1, target - nums[i], memo):
                    return True
            memo[(start, target)] = False
            return False
    
    1. DP/recursive with memorization:
       def canPartition(self, nums):
            nums.sort()
            s = sum(nums)
            if s % 2: return False
            s = s / 2
    
            def helper(nums, index, target, memo):
                if index >= len(nums):
                    return False
                if (index, target) in memo:
                    return memo[(index, target)]
                if target == nums[index]:
                    return True
                if target < nums[index]:
                    return False
                if helper(nums, index + 1, target - nums[index], memo):
                    return True
                else:
                    memo[(index + 1, target - nums[index])] = False
                if helper(nums, index + 1, target, memo):
                    return True
                else:
                    memo[(index + 1, target)] = False
                return False
    
            return helper(nums, 0, s, {})
    

Log in to reply
 

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