from typing import List

# Naive approach
# def findTargetSumWays(nums: List[int], target: int) -> int:
#     def get_target_sum(nums_list: List[int], cur_sum: int) -> int:
#         if not nums_list:
#             return int(cur_sum == target)
#
#         return get_target_sum(nums_list[1:], cur_sum + nums_list[0]) + get_target_sum(nums_list[1:],
#                                                                                       cur_sum - nums_list[0])
#
#     return get_target_sum(nums, 0)

# DFS
# def findTargetSumWays(nums: List[int], target: int) -> int:
#     cache, length_list = {}, len(nums)
#
#     def get_target_sum(index: int, current_sum: int) -> int:
#
#         if index == length_list:
#             cache[(index, current_sum)] = int(current_sum == 0)
#
#         if (index, current_sum) not in cache:
#             cache[(index, current_sum)] = get_target_sum(index + 1, current_sum + nums[index]) + get_target_sum(
#                 index + 1, current_sum - nums[index])
#
#         return cache[(index, current_sum)]
#
#     return get_target_sum(0, target)

# DP
def findTargetSumWays(nums: List[int], target: int) -> int:
    index = len(nums) - 1
    curr_sum = 0
    memo = {}

    def dp(nums, target, index, curr_sum):
        if (index, curr_sum) in memo:
            return memo[(index, curr_sum)]

        if index < 0 and curr_sum == target:
            return 1
        if index < 0:
            return 0

        positive = dp(nums, target, index - 1, curr_sum + nums[index])
        negative = dp(nums, target, index - 1, curr_sum + -nums[index])

        memo[(index, curr_sum)] = positive + negative
        return memo[(index, curr_sum)]

    return dp(nums, target, index, curr_sum)
from typing import List

# Naive approach
# def findTargetSumWays(nums: List[int], target: int) -> int:
#     def get_target_sum(nums_list: List[int], cur_sum: int) -> int:
#         if not nums_list:
#             return int(cur_sum == target)
#
#         return get_target_sum(nums_list[1:], cur_sum + nums_list[0]) + get_target_sum(nums_list[1:],
#                                                                                       cur_sum - nums_list[0])
#
#     return get_target_sum(nums, 0)

# DFS
# def findTargetSumWays(nums: List[int], target: int) -> int:
#     cache, length_list = {}, len(nums)
#
#     def get_target_sum(index: int, current_sum: int) -> int:
#
#         if index == length_list:
#             cache[(index, current_sum)] = int(current_sum == 0)
#
#         if (index, current_sum) not in cache:
#             cache[(index, current_sum)] = get_target_sum(index + 1, current_sum + nums[index]) + get_target_sum(
#                 index + 1, current_sum - nums[index])
#
#         return cache[(index, current_sum)]
#
#     return get_target_sum(0, target)

# DP
def findTargetSumWays(nums: List[int], target: int) -> int:
    index = len(nums) - 1
    curr_sum = 0
    memo = {}

    def dp(nums, target, index, curr_sum):
        if (index, curr_sum) in memo:
            return memo[(index, curr_sum)]

        if index < 0 and curr_sum == target:
            return 1
        if index < 0:
            return 0

        positive = dp(nums, target, index - 1, curr_sum + nums[index])
        negative = dp(nums, target, index - 1, curr_sum + -nums[index])

        memo[(index, curr_sum)] = positive + negative
        return memo[(index, curr_sum)]

    return dp(nums, target, index, curr_sum)
# Naive approach # def findTargetSumWays(nums: List[int], target: int) -> int: #     def get_target_sum(nums_list: List[int], cur_sum: int) -> int: #         if not nums_list: #             return int(cur_sum == target) # #         return get_target_sum(nums_list[1:], cur_sum + nums_list[0]) + get_target_sum(nums_list[1:], #                                                                                       cur_sum - nums_list[0]) # #     return get_target_sum(nums, 0) # DFS # def findTargetSumWays(nums: List[int], target: int) -> int: #     cache, length_list = {}, len(nums) # #     def get_target_sum(index: int, current_sum: int) -> int: # #         if index == length_list: #             cache[(index, current_sum)] = int(current_sum == 0) # #         if (index, current_sum) not in cache: #             cache[(index, current_sum)] = get_target_sum(index + 1, current_sum + nums[index]) + get_target_sum( #                 index + 1, current_sum - nums[index]) # #         return cache[(index, current_sum)] # #     return get_target_sum(0, target) # DP