<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:
        total_sum = sum(nums)
        
        # If the target is unreachable, return 0
        if abs(target) > total_sum:
            return 0
        
        # Initialize the DP array
        # The range of possible sums is [-total_sum, total_sum]
        # We add total_sum as an offset to handle negative sums
        dp = [[-1] * (2 * total_sum + 1) for _ in range(len(nums))]
        
        def calculate(index: int, current_sum: int) -> int:
            # Base case: if we've used all numbers
            if index == len(nums):
                return 1 if current_sum == target else 0
            
            # Map the current_sum to a non-negative index
            sum_index = current_sum + total_sum
            
            # Check if we've already computed this state
            if dp[index][sum_index] != -1:
                return dp[index][sum_index]
            
            # Recursive cases:
            # 1. Add the current number
            add = calculate(index + 1, current_sum + nums[index])
            
            # 2. Subtract the current number
            subtract = calculate(index + 1, current_sum - nums[index])
            
            # Store the result in dp array
            dp[index][sum_index] = add + subtract
            
            return dp[index][sum_index]
        
        # Start the recursion from index 0 with initial sum 0
        return calculate(0, 0)
        
22628