Recursion & DP Target: 15s
Transform target sum into a subset-sum problem via (total + target) / 2.
total = sum(nums)
if (total + target) % 2: return 0
s = (total + target) // 2
dp = [0] * (s + 1)
dp[0] = 1
for n in nums:
for j in range(s, n-1, -1):
dp[j] += dp[j - n]Type it from memory. Go.