Prashant Mishraclass 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;
}
}
Memoization approach: top down dp
TC :O(n*m), where n is the size of the array and m is the target sum value k
sc : O(n*m) for using dp array and O(n+m) stack space
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;
}
}
