0 1 backpack problem
Method 1 DFS with memorization
class Solution:
def canPartition(self, nums: List[int]) -> bool:
#TC: O(m*T)
#SC: O(m*T) max
Sum = sum(nums)
if Sum % 2 == 1:
return False
T = Sum // 2
m = len(nums)
Dict = {}
def helper(target, start):
if (start, target) in Dict:
return Dict[(start, target)]
if target == 0:
Dict[(start, target)] = True
return True
if target < 0:
Dict[(start, target)] = False
return False
for i in range(start, m):
if helper(target - nums[i], i+1):
Dict[(start, target)] = True
return True
Dict[(start, target)] = False
return False
return helper(T, 0)
Method 2 DP
class Solution:
def canPartition(self, nums: List[int]) -> bool:
#TC: O(m*T)
#SC: O(m*T)
Sum = sum(nums)
if Sum % 2 == 1:
return False
T = Sum // 2
m = len(nums)
dp = [[0]*(T+1) for _ in range(m+1)]
#dp[i][j] = 1, if the first i-1 (inclusive) elements have a subset, which sums up to number j
for i in range(m+1):
dp[i][0] = 1
for i in range(1, m+1):
for j in range(1, T+1):
if dp[i-1][j] == 1:
dp[i][j] = 1
elif j-nums[i-1] >= 0 and dp[i-1][j-nums[i-1]] == 1:
dp[i][j] = 1
return dp[-1][-1]
Method 3 DP with memory reduction
class Solution:
def canPartition(self, nums: List[int]) -> bool:
#TC: O(m*T)
#SC: O(T)
Sum = sum(nums)
if Sum % 2 == 1:
return False
T = Sum // 2
m = len(nums)
dp = [0]*(T+1)
dp[0] = 1
#dp[j] = 1, if the first i-1 (inclusive) elements have a subset, which sums up to number j
for i in range(1, m+1):
prev = dp.copy()
for j in range(1, T+1):
if dp[j] == 0 and j-nums[i-1] >= 0 and prev[j-nums[i-1]] == 1:
dp[j] = 1
return dp[-1]