class Solution(object):

    def findTargetSumWays(self, nums, S):

        col = collections.defaultdict(list)
        ans = 0

        def helpf(nums, S, sum, index):
            nonlocal col
            nonlocal ans

            if index == len(nums):
                if sum == S:
                    ans += 1
            else:
                col[(sum, index)] = 0
                helpf(nums, S, sum + nums[index], index+1)
                helpf(nums, S, sum - nums[index], index+1)

        helpf(nums, S, 0, 0)
        return ans