Problem Description

The Target Sum problem asks you to determine how many ways you can assign either a plus (+) or minus (-) sign to each number in a given list of integers nums so that the resulting expression evaluates to a specified target value.

• You must use every number in nums exactly once.
• Each number can be preceded by either a + or - sign.
• Your goal is to count the total number of different ways to assign signs so that the sum equals target.

Example:
Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Explanation: There are 5 ways to assign signs to make the sum equal to 3.

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums) <= 1000
• -1000 <= target <= 1000

Thought Process

At first glance, it seems we need to try every possible combination of + and - signs for each number in nums. For each combination, we check whether the resulting sum matches the target. This is a classic brute-force approach, where each number has two choices (plus or minus), leading to 2^n possible combinations for n numbers.

However, as the list grows, the number of combinations increases exponentially, making brute-force impractical for larger inputs. To optimize, we look for overlapping subproblems: if we know the number of ways to reach a certain sum at a certain index, we can reuse that calculation. This hints at using dynamic programming (DP) to store and reuse results, dramatically improving efficiency.

The key insight is to represent the problem as a state: at position i in the list, what is the number of ways to reach a cumulative sum of s? By caching these states, we avoid recomputation.

Solution Approach

We solve the problem using a recursive depth-first search (DFS) with memoization (top-down DP). Here’s how we break it down:

1. Define the state: Let dfs(i, curr_sum) be the number of ways to reach target starting from index i with a cumulative sum of curr_sum.
2. Base case: If i == len(nums), check if curr_sum == target. If so, return 1 (found a valid way); otherwise, return 0.
3. Recursive case: For the current number, try both adding and subtracting it:
   • dfs(i+1, curr_sum + nums[i])
   • dfs(i+1, curr_sum - nums[i])
   The total number of ways is the sum of these two recursive calls.
4. Memoization: Use a cache (e.g., a dictionary) to store already computed (i, curr_sum) pairs to avoid redundant calculations.

Alternatively, a bottom-up DP (tabulation) approach can also be used, but the recursive memoized solution is often more intuitive for beginners.

Why use a hash map for memoization? Because the possible values of curr_sum can be negative and positive, so we can't use a simple array indexed by sum.

Example Walkthrough

Let’s walk through the example: nums = [1, 1, 1, 1, 1], target = 3.

1. At index 0, sum = 0. We can add or subtract the first 1:
   • Add: go to index 1, sum = 1
   • Subtract: go to index 1, sum = -1
2. At each step, repeat this process for the next number. The recursion tree branches at every index, exploring all possible combinations of plus and minus.
3. When we reach the end (index 5), we check if the sum equals 3. If so, it’s a valid way, and we count it.
4. After exploring all paths, the total number of valid ways is 5.

Visualization: Each path through the recursion tree represents a sequence of +/- choices. Only those that sum to 3 are counted.

Time and Space Complexity

• Brute-force: O(2^n) time and O(n) space (for recursion stack), where n is the length of nums. This is because each number has two choices.
• Optimized (DP with memoization): O(n * S) time and space, where S is the sum of all numbers times 2 (to handle negative and positive sums). Each unique state (i, curr_sum) is computed only once.
• The use of a hash map (dictionary) for memoization is necessary because curr_sum can be negative.

Summary

The Target Sum problem is a classic example of using recursion and dynamic programming to efficiently explore a large search space. The key insight is to recognize overlapping subproblems and cache results using memoization, reducing the exponential brute-force approach to a much more manageable polynomial time solution. By carefully structuring the recursive state and using a hash map for memoization, we can solve even the largest allowed inputs efficiently and elegantly.

Code Implementation

from typing import List
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        memo = {}
        def dfs(i, curr_sum):
            if i == len(nums):
                return 1 if curr_sum == target else 0
            key = (i, curr_sum)
            if key in memo:
                return memo[key]
            plus = dfs(i + 1, curr_sum + nums[i])
            minus = dfs(i + 1, curr_sum - nums[i])
            memo[key] = plus + minus
            return memo[key]
        return dfs(0, 0)
      

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<string, int> memo;
        return dfs(nums, 0, 0, target, memo);
    }
    
    int dfs(vector<int>& nums, int i, int curr_sum, int target, unordered_map<string, int>& memo) {
        if (i == nums.size()) return curr_sum == target ? 1 : 0;
        string key = to_string(i) + "," + to_string(curr_sum);
        if (memo.count(key)) return memo[key];
        int plus = dfs(nums, i + 1, curr_sum + nums[i], target, memo);
        int minus = dfs(nums, i + 1, curr_sum - nums[i], target, memo);
        memo[key] = plus + minus;
        return memo[key];
    }
};
      

import java.util.*;

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        Map<String, Integer> memo = new HashMap<>();
        return dfs(nums, 0, 0, target, memo);
    }
    
    private int dfs(int[] nums, int i, int currSum, int target, Map<String, Integer> memo) {
        if (i == nums.length)
            return currSum == target ? 1 : 0;
        String key = i + "," + currSum;
        if (memo.containsKey(key))
            return memo.get(key);
        int plus = dfs(nums, i + 1, currSum + nums[i], target, memo);
        int minus = dfs(nums, i + 1, currSum - nums[i], target, memo);
        memo.put(key, plus + minus);
        return plus + minus;
    }
}
      

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    const memo = new Map();
    function dfs(i, currSum) {
        if (i === nums.length) {
            return currSum === target ? 1 : 0;
        }
        const key = i + ',' + currSum;
        if (memo.has(key)) return memo.get(key);
        const plus = dfs(i + 1, currSum + nums[i]);
        const minus = dfs(i + 1, currSum - nums[i]);
        memo.set(key, plus + minus);
        return plus + minus;
    }
    return dfs(0, 0);
};