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); } } 
Top comments (0)