from collections import Counter

class Solution:
    def get_results(self, nums: List[int]) -> Counter:
        layer = [nums[0], -nums[0]]
        for num in nums[1:]:
            new_layer = []
            for item in layer:
                for val in [-num, num]:
                    new_layer.append(item + val)
            layer = new_layer
        return Counter(layer)
    
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if n == 1:
            return [0, 1][nums[0] == target or -nums[0] == target]
        half = n // 2
        left = self.get_results(nums[:half])
        right = self.get_results(nums[half:])
        ans = 0
        for lkey, lcnt in left.items():
            rcnt = right[target - lkey]
            ans += rcnt * lcnt
        return ans