1
class Solution:
2
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
3
        @cache
4
        def dfs(i, sum_):
5
            if i == len(nums):
6
                if sum_ == target:
7
                    return 1
8
                else:
9
                    return 0
10
            return dfs(i + 1, sum_ + nums[i]) + dfs(i + 1, sum_ - nums[i])
11

12
        if abs(target) > sum(nums):
13
            return 0
14
        return dfs(0, 0)