Solutions

# Top down or bottom up DP. 2 choices: pick positive or pick negative.
# dp

# Top down DP - O(n*m) time, O(n*m) space
def findTargetSumWays(nums: list[int], target: int) -> int:
    dp = {}

    def dfs(i: int, curr: int) -> int:
        if i == len(nums):
            if curr == target:
                return 1
            else:
                return 0
        elif (i, curr) in dp:
            return dp[(i, curr)]

        # pick positive
        res = dfs(i + 1, curr + nums[i])
        # pick negative
        res += dfs(i + 1, curr - nums[i])
        dp[(i, curr)] = res
        return dp[(i,curr)]

    return dfs(0, 0)
    
# Bottom up DP - O(n*m) time, O(n*m) space
def findTargetSumWays(nums: list[int], target: int) -> int:
    from collections import defaultdict
    n = len(nums)
    dp = [defaultdict(int) for _ in range(n+1)]
    # dp[i]={S: X}: how many ways each sum S can be formed using the first i numbers
    # base case
    dp[0][0] = 1

    for i in range(n):
        for sum, count in dp[i].items():
            dp[i + 1][sum + nums[i]] += count
            dp[i + 1][sum - nums[i]] += count

    return dp[n][target]