Problem

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

  • For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Examples

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

Solution

Method 1 - DFS

This solution involves exploring every possible combination of ‘+’ and ‘-’ for each element in the nums array and calculating the number of ways to get the target sum.

Approach

  1. For each number in the nums array, we have two choices: add the number to the current sum or subtract the number from the current sum.
  2. Recursively explore both choices for each number and keep track of the current sum.
  3. If we reach the end of the array and the current sum equals the target, we count that as a valid expression.

This is how the recursive tree will look:

---
title: Recursion tree for nums = [1,1,1,1,1] and target = 3
---

graph TD

	Start([Start]) --> A1["+1"] & B1["-1"]
	
	A1 --> A2["+1"] & B2["-1"]
	B1 --> C2["+1"] & D2["-1"]
	    

	A2 --> A3["+1"] & B3["-1"]
	B2 --> Dd1["..."]
	C2 --> Dd2["..."]
	D2 --> Dd3["..."]


    A3 --> A4["+1"] & B4["-1"]
    B3 --> Dd4["..."]


    A4 --> A5["+1"] & B5["-1"]
    B4 --> C5["+1"] & D5["-1"]


classDef validExp fill:#9f6,stroke:#333,stroke-width:2px;

B5:::validExp
C5:::validExp

Code

Java
class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
        return calculate(nums, target, 0, 0);
    }
    
    private int calculate(int[] nums, int target, int index, int currentSum) {
        if (index == nums.length) {
            return currentSum == target ? 1 : 0;
        }
        
        int add = calculate(nums, target, index + 1, currentSum + nums[index]);
        int subtract = calculate(nums, target, index + 1, currentSum - nums[index]);
        
        return add + subtract;
    }
}
Python
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        def calculate(index: int, current_sum: int) -> int:
            if index == len(nums):
                return 1 if current_sum == target else 0
            
            add = calculate(index + 1, current_sum + nums[index])
            subtract = calculate(index + 1, current_sum - nums[index])
            
            return add + subtract
        
        return calculate(0, 0)

Complexity

  • ⏰ Time complexity: O(2^n), where n is the number of elements in nums because at each element, we branch into two recursive calls.
  • 🧺 Space complexity: O(n), due to the depth of the recursion tree.

Method 2 - Top Down DP with memoization

  1. We use a dictionary to store the results of subproblems, where the key is a tuple (index, current_sum) and the value is the number of ways to get the target sum starting from that index with the given current sum.
  2. When we encounter a subproblem result that we have already computed previously, we return the stored result instead of recalculating it.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    
    public int findTargetSumWays(int[] nums, int target) {
        return calculate(nums, target, 0, 0);
    }
    
    private int calculate(int[] nums, int target, int index, int currentSum) {
        if (index == nums.length) {
            return currentSum == target ? 1 : 0;
        }
        
        String key = index + "," + currentSum;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        int add = calculate(nums, target, index + 1, currentSum + nums[index]);
        int subtract = calculate(nums, target, index + 1, currentSum - nums[index]);
        
        int result = add + subtract;
        memo.put(key, result);
        
        return result;
    }
}
Python
class Solution:
    def __init__(self):
        self.memo: Dict[Tuple[int, int], int] = {}
    
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        def calculate(index: int, current_sum: int) -> int:
            if index == len(nums):
                return 1 if current_sum == target else 0
            
            if (index, current_sum) in self.memo:
                return self.memo[(index, current_sum)]
            
            add = calculate(index + 1, current_sum + nums[index])
            subtract = calculate(index + 1, current_sum - nums[index])
            
            self.memo[(index, current_sum)] = add + subtract
            return self.memo[(index, current_sum)]
        
        return calculate(0, 0)

Complexity

  • ⏰ Time complexity: O(n * 2*sum), where n is the number of elements in nums and sum is the sum of the absolute values of nums.
  • 🧺 Space complexity: O(n * 2*sum), due to the space required to store the memoization table.

Method 3 - Top Down DP

In the bottom-up approach, we use a DP table where dp[i][j] represents the number of ways to get sum j using the first i elements of nums. We use one table to store the results and iterate through the array to fill up this table iteratively.

  1. Initialise a DP array of size (n+1) x (2*sum + 1) where sum is the sum of the absolute values of nums.
  2. Set the base case: dp[0][sum] = 1, which corresponds to achieving a zero sum with zero elements.
  3. Populate the DP table: for each element, update the DP table for both addition and subtraction.
  4. Return the value stored in dp[n][target + sum].

Code

Java
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += Math.abs(num);
        }
        if (target > sum || target < -sum) {
            return 0;
        }

        int[][] dp = new int[nums.length + 1][2 * sum + 1];
        dp[0][sum] = 1;

        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= 2 * sum; j++) {
                if (dp[i-1][j] != 0) {
                    if (j + nums[i - 1] <= 2 * sum) {
                        dp[i][j + nums[i - 1]] += dp[i-1][j];
                    }
                    if (j - nums[i - 1] >= 0) {
                        dp[i][j - nums[i - 1]] += dp[i-1][j];
                    }
                }
            }
        }

        return dp[nums.length][target + sum];
    }
}
Python
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(abs(num) for num in nums)
        if target > total_sum or target < -total_sum:
            return 0
        
        dp = [[0] * (2 * total_sum + 1) for _ in range(len(nums) + 1)]
        dp[0][total_sum] = 1
        
        for i in range(1, len(nums) + 1):
            for j in range(2 * total_sum + 1):
                if dp[i-1][j] != 0:
                    if j + nums[i - 1] <= 2 * total_sum:
                        dp[i][j + nums[i - 1]] += dp[i-1][j]
                    if j - nums[i - 1] >= 0:
                        dp[i][j - nums[i - 1]] += dp[i-1][j]
        
        return dp[len(nums)][target + total_sum]

Complexity

  • ⏰ Time complexity: O(n * 2*sum), where n is the number of elements in nums and sum is the sum of the absolute values of nums.
  • 🧺 Space complexity: O(n * 2*sum)