class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        SUM = 0
        for num in nums:
            SUM += num
            
        if SUM < S or (SUM + S) %2 == 1:
            return 0
        
        SUM = (SUM + S) /2
        DP = [0] *(SUM + 1)
        DP[0] = 1
        
        for num in nums:
            for i in reversed(range(len(DP))):
                if i - num >=0:
                    DP[i] = DP[i] + DP[i - num]
                else:
                    break
        return DP[-1]