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

import numpy as np
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        """
        All nums are non-negative.
        Handle 0 differently? + and - give same sum, but are distinct valid expressions.
        What do they mean by 0 <= sum(nums[i]) <= 1000?
            Is it the sum of nums[i] over all i?
            Assuming it is.
            This means if we go over the target, we can still possibly lower the sum back to target using the minus sign.
            This means the widest range is actually (-1000, 1000)
            Might have to map these ranges to negative for arrays or use a shift.
            
        Want to iterate over each i in nums, adding new nums each time.
        Want to store intermediate results / subtargets as we need multiple nums[i] to sum up to target.
        
        Need to use all nums, but options are + or -, so will be +1 only for each path unless that path has been reached before.
        
        Let TSW[i][amt] be the number of different expressions we can build, which evaluates to `amt`, using the first `i`+1 nums.
        
        Final Answer: TSW[n-1][target]
        
        Base Cases:
            TSW[0][nums[0]] = TSW[0][-nums[0]] = 1 if nums[0] != 0
            TSW[0][nums[0]] = 2 if nums[0] == 0
            # or if allocating dummy var for TSW[-1][0],
            #  then TSW[-1][0] = 1 ; # since 1 way to make empty expr that sums to 0
            #  then TSW[0][j] = ... # same as recursive case ; waste of ops here
            
        Recursive Cases:
            TSW[i][j] = TSW[i-1][j] * 2 if nums[i] == 0
            # sum( (old combo) + 0 ) = sum(old combo)
            # sum( (old combo) - 0 ) = sum(old combo)
            
            TSW[i][j] = TSW[i-1][j-nums[i]] + TSW[i-1][j+nums[i]] if nums[i] != 0
            # sum( combosThatSumTo(j-nums[i]), +nums[i] ) = j
            # sum( combosThatSumTo(j+nums[i]), -nums[i] ) = j
            # prev TSW[i-1][j] combos doesn't count
            #   towards TSW[i][j] unless nums[i] == 0
            
            Combined: TSW[i][j] = TSW[i-1][j-nums[i]] + TSW[i-1][j+nums[i]]
            
        Order of Evaluation:
            For i := 0 -> n (OR i := n -> 0; if we formulate it the opposite way),
                Evaluate TSW[i][j] for all j
                (any order since not dependent on same iter)
        
        There are 2001 values in [-1000, 1000], that is, 2000 for [-1000, -1] + [1, 1000] and 1 more value for [0, 0].
        Time Complexity: O(n * sum(nums)) = O(n * 2001) = O(n)
        Space complexity: O(n * sum(nums)) = O(n * 2001) = O(n)
        
        Potential Optimizations:
            Reduce TSW[i][amt] to a TSW[amt], iterating over `i` in the for loop.
                Reduces space complexity to O(sum(nums)) = O(2001) = O(1)
            Use += and -= instead if/elses ?
            Check if target is reachable by sum.
        """
        # use TSW[getIdx(amt)] or TSW[amt]; since TSW[-1] would give last elem
        def getIdx(amt: int) -> int:
            """Given a number `amt` representing the amount for TSW,
                return corresponding index in the TSW array.
                
                getIdx: [-1000, 1000] -> [0, 2000]
                
                # Example
                amt: [-1000, ..., -1, 0, 1, ..., 1000]
                getIdx(amt): [1001, ..., 2000, 0, 1, ..., 1000]
            """
            return amt + maxSum
        
        if (maxSum := sum(nums)) < abs(target):
            return 0 # can't reach target even if set all signs to be the same
        
        n = len(nums)
        TSW = np.zeros(maxSum*2+1, int)
        
        # Base Cases:
        TSW[getIdx(nums[0])] += 1
        TSW[getIdx(-nums[0])] += 1
        
        i = 1
        while i < n:
            newTSW = np.zeros(maxSum*2+1, int)
            
            for j in range(-maxSum, maxSum+1):
                lo, midx, hi = j-nums[i], getIdx(j), j+nums[i]
                
                if -maxSum <= lo <= maxSum:
                    newTSW[midx] += TSW[getIdx(lo)]
                if -maxSum <= hi <= maxSum:
                    newTSW[midx] += TSW[getIdx(hi)]
                
            TSW = newTSW
            i += 1
        
        return TSW[getIdx(target)]
    
    # could be faster (although same time complexity) with top-down DFS
28536