<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 {
//     int n;

// public:
//     int f(int ind, int target, vector<int>& nums) {

//         if (ind == n) {
//             if (target == 0)
//                 return 1;
//             return 0;
//         }

//         return f(ind + 1, target - nums[ind], nums) +
//                f(ind + 1, target + nums[ind], nums);
//     }
//     int findTargetSumWays(vector<int>& nums, int target) {
//         n = nums.size();
//         // return f(0, target, nums);
//         int sum = accumulate(nums.begin(), nums.end(), 0);
//         if (abs(target) > sum)
//             return 0;

//         int off = sum;
//         vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0));
//         dp[n][off] = 1;
//         for (int i = n - 1; i >= 0; i--) {
//             for (int j = -sum; j <= sum; j++) {
//                 if (j + off >= nums[i])
//                     dp[i][j + off] += dp[i + 1][j + off - nums[i]];
//                 if (j + off + nums[i] <= 2 * sum)
//                     dp[i][j + off] += dp[i + 1][j + off + nums[i]];
//             }
//         }
//         return dp[0][target + off];
//     }
// };

class Solution {
    int n;
 public:
    // int f(int ind, int target, vector<int>& nums) {

    //     if (ind == n) {
    //         if (target == 0)
    //             return 1;
    //         return 0;
    //     }

    //     return f(ind + 1, target - nums[ind], nums) +
    //            f(ind + 1, target + nums[ind], nums);
    // }
    int findTargetSumWays(vector<int>& nums, int target) {
        n = nums.size();
        // return f(0, target, nums);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (abs(target) > sum)
            return 0;

        int off = sum;
        vector<int> prev(2 * sum + 1, 0), curr(2 * sum + 1, 0);
        prev[off] = 1;
        for (int i = n - 1; i >= 0; i--) {
            fill(curr.begin(), curr.end(), 0);
            for (int j = -sum; j <= sum; j++) {
                if (j + off >= nums[i])
                    curr[j + off] += prev[j + off - nums[i]];
                if (j + off + nums[i] <= 2 * sum)
                    curr[j + off] += prev[j + off + nums[i]];
            }
            prev = curr;
        }
        return curr[target + off];
    }
};
13093