# 494 Target Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

```
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

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

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

* The length of the given array is positive and will not exceed 20.
* The sum of elements in the given array will not exceed 1000.
* Your output answer is guaranteed to be fitted in a 32-bit integer.

**Brute Force:**

**The Idea:** Before we can understand the dynammic approach, I like to lay down the solution first using brute force. This allows me to see the entire structure on it's own so I can then identify patterns and substructures. Using DFS, we can explore all possible operators on the array. The structure for array \[1,5,1], S=5 is shown below. The children are defined as the + or - sum from the parent. Any time we reach a leaf (summed all the elements of the array) and the sum is the target, then we can increment our solution by 1.

![](/files/-LoJIq9ECEr9_2T5VnRq)

**Complexity:** O(2^N) time and O(N) space

```python
import operator


class Solution:
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        if not nums:
            return 0

        root = {'sum':0, 'iter':-1}
        sol = [0]

        def dfs(node, op):
            next_iter = node['iter'] + 1
            if next_iter >= len(nums):
                return
            else:
                target_num = nums[next_iter]
                next_sum = op(node['sum'], target_num)
                if next_sum is S and next_iter + 1 >= len(nums):
                    sol[0] += 1

                dfs({'sum': next_sum, 'iter': next_iter}, operator.add)
                dfs({'sum': next_sum, 'iter': next_iter}, operator.sub)

        dfs(root, operator.add)
        dfs(root, operator.sub)
        return sol[0]
```

**Dynammic Programming:**

**The Idea:** Looking the image above, we can identify some substructures. First, the trees are vertical mirrors images of one another. Knowing this, we can then just recurse on the positive part from the root, and if we identify a -S, we also add it to our solution, since it is going to be mirrored on the other end anyway. The special case here begin when S is 0, but that can be easily accounted for. The next thing to look at is overlapping substructure. We know that if we have an identical number on the same level, then we know that it is going to eventually lead to the same sum. So if we hash by the current sum and the level (iterator in the array), then we can make this check before we explore further down into the tree.

**Complexity:**

```python
import operator


class Solution:
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        if not nums:
            return 0

        sol = [0]
        def dfs(node, op):
            next_iter = node['iter'] + 1
            if next_iter >= len(nums):
                return
            else:
                target_num = nums[next_iter]
                next_sum = op(node['sum'], target_num)
                if (next_sum == S or next_sum == -S) \
                        and next_iter + 1 >= len(nums):
                    sol[0] += 1

                dfs({'sum': next_sum, 'iter': next_iter}, operator.add)
                dfs({'sum': next_sum, 'iter': next_iter}, operator.sub)


        dfs({'sum':0, 'iter':-1}, operator.add)
        if S == 0:
            sol[0] *= 2
        return sol[0]



obj = Solution()
print(obj.findTargetSumWays([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 0)) # 2^20
print(obj.findTargetSumWays([1000], 1000)) # 1
print(obj.findTargetSumWays([1,2,1], 0)) # 2: (-1,2,-1) and (1,-2,1)
print(obj.findTargetSumWays([1, 2, 3, 4, 5, 6, 7, 8, 9], 5)) # 22
print(obj.findTargetSumWays([1, 5, 1], 5)) # 2
print(obj.findTargetSumWays([1, 1, 1, 1, 1], 3)) # 5
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/494-target-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.