<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 {
public:

    int solve(int n,int sum,vector<int>& arr,unordered_map<string,int>&mp){
        string key=to_string(n)+" "+to_string(sum);
	   if(n==0 ){
	       if(sum==0 and arr[0]==0)return 2;
	       if(sum==0 || sum==arr[0])return 1;
	       return 0;
	   }
       
	    if(mp.find(key)!=mp.end())return mp[key];
	    int pickSum=solve(n-1,sum-arr[n],arr,mp);
	    int notPickSum=solve(n-1,sum,arr,mp);
	    return mp[key]=(pickSum+notPickSum);
	    
	    
	}
    int findTargetSumWays(vector<int>& arr, int d) {
        int n=arr.size();
        int sum=accumulate(arr.begin(),arr.end(),0);
        int target=(d+sum)/2;
        sort(arr.begin(),arr.end(),greater<int>());
        unordered_map<string,int>mp;
        return (d+sum)%2==0 ? solve(n-1,target,arr,mp):0;
    }
};
53991