Target Sum or Partition with given difference Leetcode

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);
    }
}