Target Sum

How it works

We want to count the number of ways to assign + and - signs to the numbers so that their final sum equals the target.

In the bottom-up DP approach, we used a separate data structure for each index. However, at each step, the new states depend only on the previous step, not on all earlier steps.

This means we can reuse a single data structure to keep track of all possible sums and how many ways each sum can be formed, updating it as we process each number.

Steps

1. Create a map dp where:
   • the key represents a possible sum
   • the value represents the number of ways to form that sum
2. Initialize dp[0] = 1 since there is exactly one way to reach sum 0 before using any numbers
3. For each number in the array:
   • Create a new map next_dp to store updated sums
4. For every (total, count) in dp:
   • Add the current number → update next_dp[total + num]
   • Subtract the current number → update next_dp[total - num]
5. Replace dp with next_dp after processing the current number
6. After all numbers are processed, dp[target] gives the number of valid ways
7. Return dp[target]

Complexity

• Time complexity: O(n * m)
• Space complexity: O(m)

Where n is the length of the array nums and m is the sum of all the elements in the array.

Things to watch for

Incorrect Memoization Key

When using top-down DP, the state must include both the current index and the running sum. Forgetting to include one of these in the memoization key will cause incorrect caching and wrong results. The key should be (index, total) not just index or just total.

Not Handling Negative Sums in Array-Based DP

When using an array instead of a hashmap for memoization, the running sum can become negative. You must offset the sum by the total sum of all elements to convert it to a valid non-negative index. For example, use dp[i][total + totalSum] where totalSum is the sum of all numbers.

Modifying Map While Iterating (Space-Optimized DP)

In the space-optimized bottom-up approach, you cannot update dp while iterating over it. You must create a new map next_dp for the next state and then replace dp with next_dp after processing each number. Modifying dp in place leads to using updated values in the same iteration.

from typing import List
from collections import defaultdict

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        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]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<int, int> dp;
        dp[0] = 1;

        for (int num : nums) {
            unordered_map<int, int> nextDp;
            for (auto& entry : dp) {
                int total = entry.first;
                int count = entry.second;
                nextDp[total + num] += count;
                nextDp[total - num] += count;
            }
            dp = nextDp;
        }
        return dp[target];
    }
};