Recursion & DP Target: 15s
Reduces to 0/1 knapsack: can we pick a subset summing to total/2? Backwards loop prevents item reuse.
def canPartition(nums):
total = sum(nums)
if total % 2: return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for x in nums:
for j in range(target, x - 1, -1): # backwards!
dp[j] = dp[j] or dp[j - x]
return dp[target]Type it from memory. Go.