target_sum.py

def findTargetSumWays(nums: List[int], S: int) -> int:
    totalSum = sum(nums)
    if totalSum < S or (S + totalSum) % 2 == 1:
        return 0

    n = len(nums)
    s_total = int((S+totalSum)/2)
    dp = [0 for _ in range(s_total+1)]
    dp[0] = 1
    for num in nums:
        for j in range(s_total,num-1,-1):dp[j] += dp[j - num]
    
    return dp[-1]