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

• 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, {})
``````

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