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.

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

Simple Recursive Approach

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return find(0,0,target,nums);
    }
    public int find(int index,int sum, int target, int[] nums){
        if(index>=nums.length){
            if(sum==target) return 1;
            return 0;
        }
        //we can take + for current index element
        int takePlus = find(index+1,sum+nums[index],target,nums);
        int takeMinus = find(index+1,sum-nums[index],target,nums);
        return takePlus + takeMinus;
    }
}

Optimal Approach :
Time complexity O(n*m) as n*m are the no. of possible states that we will traverse or recursively call,
Space complexity : O(n*m) + o(n) (n for auxiliary space )

//this is similar to subset sum equals to target
//example  nums = [1,1,1,1,1], target = 3
/*
-1 + 1 + 1 + 1 + 1 = 3
i.e. (1+1+1+1)-(1) = 3 i.e subsetSum1 - subsetSum2 = target , where subsetSum1 > sumbsetSum2
so, s1-s2 = t, t is target and s1>s2
since, s1+s2 = sum , sum is sum of entire array;
hence, t+s2+s2 = sum
i.e., s2 = (sum-t)/2;
//edges cases to take care of 
sum-t %2 should be 0, because (sum-t)/2 can't be fraction else s2 can't be equal to a fraction value as the array is integer.
sum-t>=0 as  sum of all the elements can't be negative
*/
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // we have to achieve the target
        int sum = Arrays.stream(nums).reduce(0,(a,b)->a+b);

        if(sum-target<0 || (sum-target)%2!=0) return 0;
        //return subsetSumEqualsToTarget(nums.length-1,(sum-target)/2,nums);
        int dp[][] = new int[nums.length][(sum-target)/2 +1];
        for(int row [] : dp) Arrays.fill(row,-1);
        return findSubsetSumCountEqualsToTarget(nums,nums.length-1,(sum-target)/2,dp);

    }
 public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target,int dp[][]){

        if(i==0){
             //since 0<=arr[i]<=1000; hence we have to check the possibility of 0 as well
            // if arr[i]==0 and target =0 then you should return 2 
            //as there are two solutions now i.e. either you will take this 0 or won't take this 0 
            //in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
            if(target ==0 && arr[i]==0) return 2; // extra line added to the usual approach because of presence of 0 in the array
            if(target==0 || arr[i]==target) return 1; // usual approach
            return 0;
        }
         if(dp[i][target]!=-1) return dp[i][target];
        int left =0;
        if(target>=arr[i]){
            left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i],dp);
        }
        int right = findSubsetSumCountEqualsToTarget(arr,i-1,target,dp);
        return dp[i][target] = (left+right);
    }
}

Target Sum or Partition with given difference Leetcode