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

# class Solution:
#     def findTargetSumWays(self, nums: List[int], target: int) -> int:

#         @cache
#         def get_num(i, cur_sum):
#             if i == 0:
#                 return int(cur_sum + nums[i] == 0) + int(cur_sum - nums[i] == 0)
            
#             return get_num(i-1, cur_sum - nums[i]) + get_num(i-1, cur_sum + nums[i])
        
#         return get_num(len(nums) - 1, target)
    
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        @cache
        def get_num(i, cur_sum):
            if i == len(nums)-1:
                return int(cur_sum + nums[i] == target) + int(cur_sum - nums[i] == target)
            
            return get_num(i+1, cur_sum - nums[i]) + get_num(i+1, cur_sum + nums[i])
        
        return get_num(0, 0)



class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        ss = sum(nums)
        amount = 2*ss+1
        
        if not -ss <= target <= ss:
            return 0
        
        dp = [[0]*(amount+1) for _ in range(len(nums))]
        
        
        for i in range(len(nums)):
            for cur_sum in range(amount+1):
                if i == 0:
                    dp[i][cur_sum] = int(cur_sum + nums[i] == target+ss) + int(cur_sum - nums[i] == target+ss)
                else:
                    if cur_sum - nums[i] >= 0:
                        dp[i][cur_sum] += dp[i-1][cur_sum - nums[i]]
                    if  cur_sum + nums[i] <= amount:
                        dp[i][cur_sum] += dp[i-1][cur_sum + nums[i]]
        import numpy as np
        
        # print(np.array(dp))

        return dp[-1][ss]
28883