Target sum

class Solution { public int findTargetSumWays(int[] nums, int target) { /* it is similar to subset sum equal to target given (+1 + 1 + 1 + 1) - (1) = 3 i.e. s1-s2 = k ( s1 and s2 are the subsets) we know s1+s2 = sum i.e k+s2+s2 = sum => s2 = (sum-k)/2 edge cases : sum-k>=0 because, 0<=nums[i]<=1000 given So,sum can't be less than 0 also (sum-k)/2 can not be fraction, as s2 can't be equal to a fraction value as the array is integer. */ int sum =0; for(int i : nums){ sum+=i; } int k = (sum-target)/2; if((sum-target)<0 || (sum-target)%2!=0) return 0; return subsetSumEqTarget(0,nums,k); } public int subsetSumEqTarget(int index, int nums[], int k){ //base case if(index == nums.length-1){ if(k ==0 && nums[index] ==k) return 2; if(k ==0 || nums[index]==k) return 1; return 0; } int take = 0; if(k>=nums[index]){ take = subsetSumEqTarget(index+1,nums,k-nums[index]); } int dontTake = subsetSumEqTarget(index+1,nums,k); return take + dontTake; } } 

class Solution { public int findTargetSumWays(int[] nums, int target) { /* it is similar to subset sum equal to target given (+1 + 1 + 1 + 1) - (1) = 3 i.e. s1-s2 = k ( s1 and s2 are the subsets) we know s1+s2 = sum i.e k+s2+s2 = sum => s2 = (sum-k)/2 edge cases : sum-k>=0 because, 0<=nums[i]<=1000 given So,sum can't be less than 0 also (sum-k)/2 can not be fraction, as s2 can't be equal to a fraction value as the array is integer. */ int sum =0; for(int i : nums){ sum+=i; } int k = (sum-target)/2; if((sum-target)<0 || (sum-target)%2!=0) return 0; int dp[][] = new int[nums.length][k+1]; for(int d[] : dp) Arrays.fill(d,-1); return subsetSumEqTarget(0,nums,k,dp); } public int subsetSumEqTarget(int index, int nums[], int k,int dp[][]){ //base case if(index == nums.length-1){ if(k ==0 && nums[index] ==k) return 2; if(k ==0 || nums[index]==k) return 1; return 0; } if(dp[index][k]!=-1) return dp[index][k]; int take = 0; if(k>=nums[index]){ take = subsetSumEqTarget(index+1,nums,k-nums[index],dp); } int dontTake = subsetSumEqTarget(index+1,nums,k,dp); return dp[index][k] = take + dontTake; } }