Target Sum

Assign + or - to each number and count expressions that sum to target. Select an approach to visualize:

At each index i we make a binary decision: add +nums[i] or subtract -nums[i] to the running total. We recurse on both choices and count paths where the final total equals target.

1. 1Define backtrack(i, total) which tries both +nums[i] and -nums[i].
2. 2Base case: when i == len(nums), return 1 if total == target, else 0.
3. 3Return the sum of left (add) and right (subtract) recursion results.
4. 4Many subproblems repeat — fixed by memoization in Approach 2.

def findTargetSumWays(self, nums, target):
    def backtrack(i, total):
        if i == len(nums):
            return 1 if total == target else 0
        return (backtrack(i+1, total+nums[i]) +
                backtrack(i+1, total-nums[i]))
    return backtrack(0, 0)

The recursion recomputes the same (i, total) states repeatedly. There are only n × (2·sum+1) unique states. Cache each result and reuse it on repeated calls.

1. 1Add dp = {} before the recursive function.
2. 2At the start of each call, check if (i, total) is in the cache. If so, return immediately (shown in amber/yellow).
3. 3Store the result before returning. Total unique computations drops from O(2ⁿ) to O(n·S).

def findTargetSumWays(self, nums, target):
    dp = {}
    def backtrack(i, total):
        if i == len(nums):
            return 1 if total == target else 0
        if (i, total) in dp: return dp[(i, total)]
        dp[(i,total)] = (backtrack(i+1, total+nums[i]) +
                        backtrack(i+1, total-nums[i]))
        return dp[(i, total)]
    return backtrack(0, 0)

Use an array of n+1 dicts where dp[i][total] = number of ways to reach total using the first i numbers. Transition: each way to reach a total splits into two ways for the next number.

1. 1Initialize dp[0][0] = 1 — one way to reach sum 0 with no numbers.
2. 2For each number nums[i], for each (total, count) in dp[i]: update dp[i+1][total±nums[i]] += count.
3. 3Answer is dp[n][target].

from collections import defaultdict
def findTargetSumWays(self, nums, target):
    n = len(nums)
    dp = [defaultdict(int) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for total, count in dp[i].items():
            dp[i+1][total + nums[i]] += count
            dp[i+1][total - nums[i]] += count
    return dp[n][target]

We only need the previous layer dp[i] to compute dp[i+1]. Replace the full 2D table with a single dict that gets replaced each iteration.

1. 1Initialize dp = {0: 1}.
2. 2For each num, build next_dp from dp using next_dp[total±num] += count.
3. 3Replace dp = next_dp after processing each number.
4. 4Answer is dp[target].

from collections import defaultdict
def findTargetSumWays(self, nums, target):
    dp = defaultdict(int)
    dp[0] = 1
    for num in nums:
        next_dp = defaultdict(int)
        for total, count in dp.items():
            next_dp[total + num] += count
            next_dp[total - num] += count
        dp = next_dp
    return dp[target]