# Leetcode 494. Target Sum

[link](https://leetcode.com/problems/target-sum/)
---

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

First, we initialize a dictionary dp to store previously computed results. The key (index, total) represents the current index in the nums array and the current total, and the value is the number of ways to reach that total from the current index.

Define a recursive function backtracking(index, total) that explores all possible combinations of adding or subtracting elements from the array nums to reach the target total starting from the index-th element.

In the recursive function:

If the index is equal to the length of nums, check if total is equal to the target. If it is, return 1 (indicating a valid way to reach the target), otherwise return 0 (indicating no valid way).

Check if the result for the current (index, total) pair is already computed in the dp dictionary. If it is, return the cached result. If not, calculate the number of ways to reach the target by either adding nums[index] or subtracting nums[index] from total. This is done by recursively calling backtracking for the next index (index + 1) with the updated total values. Store the computed result in the dp dictionary for the current (index, total) pair.

Finally, return the result of calling backtracking(0, 0) as the answer, which represents the number of ways to reach the target sum starting from the first element of nums with an initial total of 0.

#### Solution 1

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {} # (index, tot) -> # of ways
        
        def backtracking(index, total):
            if index == len(nums):
                return 1 if total == target else 0
            if (index, total) in dp:
                return dp[(index, total)]
            
            dp[(index, total)] = (backtracking(index + 1, total + nums[index]) +
                                  backtracking(index + 1, total - nums[index]))
                             
            return dp[(index, total)]
        
        return backtracking(0, 0)
        

O(T): O(n * T)
O(S): O(n)