# Target Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/target-sum)
Canonical: https://scaleengineer.com/dsa/problems/target-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array
**Companies:** [Myntra](https://scaleengineer.com/companies/myntra), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## 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`.

**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

**Constraints:**

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

# Approaches
## Brute Force Recursion
This approach uses recursion to explore every possible combination of `+` and `-` signs for the numbers in the input array. It constructs a binary decision tree where, at each level corresponding to an element in `nums`, it branches into two possibilities: adding the element or subtracting it. The total count is the number of paths in this tree that result in the target sum.
**Time:** O(2^n), where `n` is the length of the `nums` array. At each step, the function branches into two recursive calls, leading to a recursion tree with `2^n` leaf nodes. · **Space:** O(n), where `n` is the length of the `nums` array. This space is used by the recursion call stack, which can go as deep as `n`.
**Pros:** Simple to conceptualize and implement.; Provides a clear, direct translation of the problem statement into code.
**Cons:** Extremely inefficient due to its exponential time complexity.; Leads to a 'Time Limit Exceeded' error on platforms like LeetCode for all but the smallest inputs.; Recalculates the same subproblems multiple times.
### Explanation
The core idea is to build a recursive function that traverses through the `nums` array. This function keeps track of the current index being processed and the sum accumulated so far. For each number, the function calls itself twice: once for the case where the number is added to the sum, and once for the case where it's subtracted. The recursion stops when all numbers have been processed. At this point, if the accumulated sum equals the target, we have found one valid expression. The final result is the total count of all such valid expressions found across all recursive paths.

```java
class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        calculate(nums, 0, 0, target);
        return count;
    }
    public void calculate(int[] nums, int i, int sum, int target) {
        if (i == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            calculate(nums, i + 1, sum + nums[i], target);
            calculate(nums, i + 1, sum - nums[i], target);
        }
    }
}
```
### Algorithm
- Define a recursive function, say `calculate(nums, index, currentSum, target)`.
- The base case for the recursion is when `index` reaches the end of the `nums` array (`index == nums.length`).
  - If `currentSum` is equal to `target`, it means we have found a valid expression. Return 1.
  - Otherwise, return 0.
- In the recursive step, for the number at `nums[index]`, we explore both possibilities:
  1. Adding the number: Make a recursive call `calculate(nums, index + 1, currentSum + nums[index], target)`.
  2. Subtracting the number: Make a recursive call `calculate(nums, index + 1, currentSum - nums[index], target)`.
- The total number of ways is the sum of the results from these two recursive calls.
- The initial call to start the process is `calculate(nums, 0, 0, target)`.

## Recursion with Memoization
This approach optimizes the brute-force recursion by using memoization, a top-down dynamic programming technique. It avoids re-computing results for the same subproblems by storing them in a cache (e.g., a 2D array or a hash map). A subproblem is uniquely identified by the current index in the `nums` array and the current accumulated sum.
**Time:** O(n * S), where `n` is the number of elements and `S` is the total sum. The number of unique states `(index, sum)` is `n * (2*S + 1)`, and each state is computed once. · **Space:** O(n * S), where `n` is the number of elements and `S` is the total sum of elements in `nums`. This space is dominated by the memoization table. The recursion stack adds an O(n) factor.
**Pros:** Drastically improves performance over brute force by eliminating redundant computations.; Guarantees that each subproblem is solved only once.
**Cons:** Requires significant space for the memoization table, which can be large if the sum of numbers is high.; The logic for handling negative sums with an offset adds a layer of complexity.
### Explanation
The brute-force approach suffers from solving the same subproblems repeatedly. For example, reaching a sum of `S` at index `i` can happen through different paths, but the number of ways to reach the target from this state `(i, S)` is always the same. We can cache these results. We define a state by `(index, sum)`. A 2D array `memo[index][sum + offset]` is used to store the number of ways to reach the target from the current `index` with the current `sum`. The `offset` is needed because the `sum` can be negative, and array indices must be non-negative. Before any recursive computation, we check our `memo` table. If a result exists, we use it directly. Otherwise, we compute it, store it, and then return it.

```java
import java.util.Arrays;

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        if (Math.abs(target) > totalSum) {
            return 0;
        }
        
        int[][] memo = new int[nums.length][2 * totalSum + 1];
        for (int[] row : memo) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        
        return calculate(nums, 0, 0, target, memo, totalSum);
    }
    
    private int calculate(int[] nums, int i, int sum, int target, int[][] memo, int totalSum) {
        if (i == nums.length) {
            return sum == target ? 1 : 0;
        }
        
        if (memo[i][sum + totalSum] != Integer.MIN_VALUE) {
            return memo[i][sum + totalSum];
        }
        
        int add = calculate(nums, i + 1, sum + nums[i], target, memo, totalSum);
        int subtract = calculate(nums, i + 1, sum - nums[i], target, memo, totalSum);
        
        memo[i][sum + totalSum] = add + subtract;
        return memo[i][sum + totalSum];
    }
}
```
### Algorithm
- The state of a subproblem can be defined by `(index, currentSum)`.
- Create a memoization table, `memo[index][sum]`, to store the results of computed subproblems. A 2D array is suitable for this.
- Since the `sum` can be negative, map it to a non-negative index using an offset. The total sum of all numbers in `nums` can be used as this offset.
- The recursive function `calculate(index, sum)` first checks if the result for the state `(index, sum)` is already in the memoization table. If yes, it returns the stored value.
- If not, it computes the result by making the two recursive calls (for adding and subtracting `nums[index]`) as in the brute-force approach.
- Before returning, it stores the computed result in the memoization table for future use.

## 2D Dynamic Programming
This approach converts the top-down memoized recursion into a bottom-up iterative solution. It builds a 2D DP table to systematically compute the number of ways to form every possible sum using a growing subset of the input numbers, from the first element up to the last.
**Time:** O(n * S). We iterate through `n` numbers, and for each, we iterate through a range of sums of size `2*S`. · **Space:** O(n * S), where `n` is the number of elements and `S` is their total sum. This is for the 2D DP table.
**Pros:** Avoids recursion overhead, which can be slightly more efficient in practice than the memoized approach.; Systematic and easy to reason about the state transitions.
**Cons:** The space complexity is high, O(n * S), which can be a problem if the sum of numbers is large.
### Explanation
Instead of recursion, we can use a table to build up the solution iteratively. Let `dp[i][j]` be the number of ways to assign signs to the first `i` numbers in `nums` such that their sum is `j`. Again, since `j` can be negative, we use an offset. Let `S` be the sum of all numbers in `nums`. Our DP table will be `dp[nums.length + 1][2 * S + 1]`, and `dp[i][sum + S]` will store the number of ways. We start with `dp[0][S] = 1` (one way to get sum 0 with 0 numbers). Then, for each number `num` from `nums`, we iterate through the previous row of the DP table (`dp[i-1]`). For each sum `s` that had a non-zero count, we update the current row (`dp[i]`) by adding the count to `dp[i][s + num]` and `dp[i][s - num]`. After processing all numbers, the answer will be in `dp[nums.length][target + S]`.

```java
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (Math.abs(target) > totalSum) {
            return 0;
        }

        int offset = totalSum;
        int[][] dp = new int[nums.length + 1][2 * totalSum + 1];
        dp[0][offset] = 1; // Base case

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

        return dp[nums.length][target + offset];
    }
}
```
### Algorithm
- Create a 2D DP table, `dp[i][j]`, where `dp[i][j]` stores the number of ways to achieve a sum `j` using the first `i` elements of `nums`.
- Use an offset to handle negative sums. The table size will be `(n+1) x (2*S+1)`, where `n` is the number of elements and `S` is their total sum. `dp[i][sum + S]` will store the result.
- Initialize the table. The base case is `dp[0][S] = 1`, which means there is one way to get a sum of 0 with an empty set of numbers.
- Iterate from `i = 1` to `n`. For each element `nums[i-1]`, iterate through all possible sums `s`.
- The transition relation is: if `dp[i-1][s]` is greater than 0, it means sum `s - S` was achievable with `i-1` elements. We can then contribute this count to two new sums with `i` elements: `(s - S) + nums[i-1]` and `(s - S) - nums[i-1]`. So, we update `dp[i][s + nums[i-1]]` and `dp[i][s - nums[i-1]]`.
- The final answer is `dp[n][target + S]`.

## Subset Sum Problem Transformation
This highly efficient approach reformulates the problem into a classic 0/1 knapsack-style problem, specifically the "Subset Sum" problem. By using a bit of algebra, we can determine that the task is equivalent to finding the number of subsets of `nums` that sum to a specific value. This transformed problem can then be solved with a space-optimized 1D dynamic programming approach.
**Time:** O(n * S), where `n` is the number of elements and `S` is the target subset sum. This is asymptotically the same as the other DP approaches but often faster in practice as the target subset sum is smaller than the full sum range. · **Space:** O(S), where `S` is the target subset sum, which is at most the total sum of `nums`. This is a significant improvement over the O(n * S) space of previous DP approaches.
**Pros:** Most efficient in terms of space complexity.; The logic is clean, avoiding the need for negative index handling or offsets.; It's a classic and powerful DP pattern.
**Cons:** The mathematical transformation to the subset sum problem might not be immediately obvious.
### Explanation
Let the sum of numbers with a `+` sign be `sum(P)` and the sum of numbers with a `-` sign be `sum(N)`. We are looking for `sum(P) - sum(N) = target`. We know that `sum(P) + sum(N) = totalSum`. By adding these two equations, we get `2 * sum(P) = target + totalSum`, which means `sum(P) = (target + totalSum) / 2`. This transforms the problem into: find the number of subsets of `nums` that have a sum equal to `(target + totalSum) / 2`. This is a standard subset sum problem. We can solve it using a 1D DP array, `dp`, where `dp[i]` stores the number of subsets that sum to `i`. We iterate through each number in `nums` and update the `dp` array. The final answer is the value at `dp[(target + totalSum) / 2]`.

```java
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        // If (target + totalSum) is odd or target is unreachable, no solution exists.
        if (Math.abs(target) > totalSum || (target + totalSum) % 2 != 0) {
            return 0;
        }

        int subsetSum = (target + totalSum) / 2;
        
        int[] dp = new int[subsetSum + 1];
        dp[0] = 1; // Base case: one way to make sum 0 (with an empty set)

        for (int num : nums) {
            // Iterate backwards to use each number at most once per subset
            for (int j = subsetSum; j >= num; j--) {
                dp[j] = dp[j] + dp[j - num];
            }
        }

        return dp[subsetSum];
    }
}
```
### Algorithm
- Calculate `totalSum`, the sum of all elements in `nums`.
- The problem can be rephrased as finding a subset of `nums`, let's call it `P`, to which we assign `+` signs (the rest, `N`, get `-` signs). We need `sum(P) - sum(N) = target`.
- We also know `sum(P) + sum(N) = totalSum`.
- Adding these two equations yields `2 * sum(P) = target + totalSum`, which simplifies to `sum(P) = (target + totalSum) / 2`.
- The problem is now to find the number of subsets of `nums` that sum to `subsetSum = (target + totalSum) / 2`.
- Check for edge cases: if `target + totalSum` is odd or negative, no solution is possible, so return 0.
- Use a 1D DP array, `dp`, of size `subsetSum + 1`. `dp[j]` will store the number of ways to form sum `j`.
- Initialize `dp[0] = 1` (one way to make sum 0: with an empty set).
- Iterate through each `num` in `nums`. For each `num`, update the `dp` array: `dp[j] = dp[j] + dp[j - num]` for `j` from `subsetSum` down to `num`.
- The final answer is `dp[subsetSum]`.

# Solutions
### Java

```java
class Solution {
public
  int findTargetSumWays(int[] nums, int target) {
    int s = 0;
    for (int v : nums) {
      s += v;
    }
    if (s < target || (s - target) % 2 != 0) {
      return 0;
    }
    int n = (s - target) / 2;
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int v : nums) {
      for (int j = n; j >= v; --j) {
        dp[j] += dp[j - v];
      }
    }
    return dp[n];
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {number} */ var findTargetSumWays =
  function (nums, target) {
    let s = 0;
    for (let v of nums) {
      s += v;
    }
    if (s < target || (s - target) % 2 != 0) {
      return 0;
    }
    const m = nums.length;
    const n = (s - target) / 2;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= m; ++i) {
      for (let j = n; j >= nums[i - 1]; --j) {
        dp[j] += dp[j - nums[i - 1]];
      }
    }
    return dp[n];
  };

```

### Python

```python
class Solution : def findTargetSumWays ( self , nums : List [ int ], target : int ) -> int : s = sum ( nums ) if s < target or ( s - target ) % 2 != 0 : return 0 n = ( s - target ) // 2 dp = [ 0 ] * ( n + 1 ) dp [ 0 ] = 1 for v in nums : for j in range ( n , v - 1 , - 1 ): dp [ j ] += dp [ j - v ] return dp [ - 1 ]
```

### CPP

```cpp
class Solution { public: int findTargetSumWays ( vector < int >& nums , int target ) { int s = accumulate ( nums . begin (), nums . end (), 0 ); if ( s < target || ( s - target ) % 2 != 0 ) return 0 ; int n = ( s - target ) / 2 ; vector < int > dp ( n + 1 ); dp [ 0 ] = 1 ; for ( int & v : nums ) for ( int j = n ; j >= v ; -- j ) dp [ j ] += dp [ j - v ]; return dp [ n ]; } };
```