You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.


	For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".


Return the number of different expressions that you can build, which evaluates to target.

&nbsp;
Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: 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


Example 2:

Input: nums = [1], target = 1
Output: 1


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 20
	0 &lt;= nums[i] &lt;= 1000
	0 &lt;= sum(nums[i]) &lt;= 1000
	-1000 &lt;= target &lt;= 1000


class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @cache
        def dfs(i, sum_):
            if i == len(nums):
                if sum_ == target: return 1
                else: return 0
            return dfs(i+1, sum_+nums[i]) + dfs(i+1, sum_-nums[i])
        if abs(target) > sum(nums): return 0
        return dfs(0, 0)
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i:nums){
            sum += i;
        }
        if(target>sum || target<-sum || ((target+sum)&1)!=0) return 0;
        return subsetSum(nums,(target+sum)/2);
    }
    private int subsetSum(int[] nums,int target){
        int[][] dp = new int[nums.length+1][target+1];
        dp[0][0] = 1;
        
        for(int i=1;i<nums.length+1;i++){
            for(int j=0;j<target+1;j++){
                if(nums[i-1]<=j){
                    dp[i][j] += dp[i-1][j-nums[i-1]] + dp[i-1][j];
                }
                else dp[i][j] += dp[i-1][j];
            }
        }
        return dp[nums.length][target];
    }
}
class Solution { // YAA
public:
    
    int solve(vector<int>& nums, int target, int idx, unordered_map<string, int> &dp) {
        if(idx == nums.size()) {
            if(target == 0) {
                return 1;
            }
            return 0;
        }
        string key = to_string(idx) + " " + to_string(target);
        if(dp.find(key) != dp.end()) {
            return dp[key];
        }
        // +
        int x = solve(nums, target - nums[idx], idx+1, dp);
        // -
        int y = solve(nums, target + nums[idx], idx+1, dp);
        // sum
        return dp[key] = x+y;
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<string, int> dp;
        return solve(nums, target, 0, dp);
    }
};
var findTargetSumWays = function(nums, target) {
    const memo = new Map()
    return backtrack(0, 0)
    
    function backtrack(i, cur){
        const key = `${i} ${cur}`
        if(i == nums.length) return cur == target ? 1 : 0
        if(!memo.has(key)) memo.set(key, backtrack(i + 1, -nums[i] + cur) + backtrack(i + 1, nums[i] + cur))
        return memo.get(key)
    }
};
Target Sum