<p>You are given an integer array <code>nums</code> and an integer <code>target</code>.</p>

<p>You want to build an <strong>expression</strong> out of nums by adding one of the symbols <code>&#39;+&#39;</code> and <code>&#39;-&#39;</code> before each integer in nums and then concatenate all the integers.</p>

<ul>
	<li>For example, if <code>nums = [2, 1]</code>, you can add a <code>&#39;+&#39;</code> before <code>2</code> and a <code>&#39;-&#39;</code> before <code>1</code> and concatenate them to build the expression <code>&quot;+2-1&quot;</code>.</li>
</ul>

<p>Return the number of different <strong>expressions</strong> that you can build, which evaluates to <code>target</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1,1,1], target = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> 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
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1], target = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 20</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>0 &lt;= sum(nums[i]) &lt;= 1000</code></li>
	<li><code>-1000 &lt;= target &lt;= 1000</code></li>
</ul>

'''
The brute force and simpler approach is to try every combination of -s and +s
and check which ones sum to the target. This would be O(2^N) time complexity.

Memmoization:
At index i with total sum of x, we want to know in how many ways its possible
to sum to the target using the rest of the array. 
because at index i with a sum of x, there may be multiple combinations using 
the first i numbers that sum to x. So if we memoize, if we reach a second
combination (and any more after that) that give the same sum at index i as
a previous sum, then the answer will be the exact same and we can just
use the memoized value instead of trying every combination again.
Example:
+2, -1, -2,  4, 5, 6
-2, -1, +2,  4, 5, 6
         i

If we get to position i, on the second combination, it also sums to -1. So answering
"can we use the rest of the numbers + -1 to sum to the target" will be the same, therefore
we can memoize. This would save more and more time as the combinations grow larger.

More examples:
-1, -2, 3,  4, 5, 6
 1, 2, -3,  4, 5, 6
        i

 1, 2, 3, 4, -5,   6
1, -2, -3, 4, 5,   6
              i

'''
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        memo = [[0] * 2001 for _ in range(len(nums))]
        def find(i, so_far):
            if i == len(nums):
                return int(so_far == target)
            elif memo[i][1000 + so_far]:
                return memo[i][1000 + so_far]

            ways1 = find(i+1, so_far + nums[i])
            ways2 = find(i+1, so_far + -nums[i])

            ans = ways1 + ways2
            memo[i][1000 + so_far] = ans
            return ans

        return find(0, 0) 

'''
[1,1,1,1,1]
3
[1]
1
[16,40,9,17,49,32,30,10,38,36,31,22,3,36,32,2,26,17,30,47]
-49
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
-20
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
-28
[100,100,100,100,100,100,100,100,100,100]
-1000
[100,100,100,100,100,100,100,100,100,100]
1000
'''
26103