from collections import defaultdict

class Solution:
    def target_sum(self, nums, target):
        if not nums:
            return 0
        
        sums = defaultdict(int)
        sums[0] = 1

        running = nums[:]

        for i in range(len(running) - 2, -1, -1):
            running[i] += running[i + 1]

        for i, num in enumerate(nums):
            new_sums = defaultdict(int)
            for old_sum in sums:
                if target <= old_sum + running[i]: # if I can reach the target from this sum
                    new_sums[num + old_sum] += sums[old_sum]
                if target >= old_sum - running[i]:
                    new_sums[old_sum - num] += sums[old_sum]

            sums = new_sums
        
        return sums[target]

nums = [1, 1, 1, 1, 1]
target = 3
solution = Solution()
print(solution.target_sum(nums, target))
        
