Target Sum LeetCode
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int i=0;i<nums.length;i++){
sum=sum+nums[i];
}
if((sum+target)%2!=0 || target>sum || target<-sum){
return 0;
}
else{
int val=(sum+target)/2;
int t[][]=new int[nums.length+1][val+1];
int count0=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
count0++;
}
}
//System.out.println(count0);
for(int i=0;i<nums.length+1;i++){
for(int j=0;j<val+1;j++){
if(i==0){
t[i][j]=0;
}
if(j==0){
t[i][j]=1;
}
}
}
for(int i=1;i<nums.length+1;i++){
for(int j=1;j<val+1;j++){
if(nums[i-1]>j || nums[i-1]==0){
t[i][j]=t[i-1][j];
}
else{
t[i][j]=((t[i-1][j]) + (t[i-1][j-nums[i-1]]));
}
}
}
return t[nums.length][val]*(int)(Math.pow(2,count0));
}
}
}
Approach:
1. For some elements we have to put positive and for some elements, we have to put negative. So we should assume that we have two packets P1 and P2. In P1 we have all positive elements and P2 all negative elements.
2. Since now we want the count of the number of times we can make sum of elements in given array equal to the target by taking different elements at different times. So for this, we need to get a number of times the sum of elements in P1 + Sum of elements in P2 is equal to the target.
Since P2 has all negative elements, so its sum will also be negetive. So if P1 sum is S1 and P2 sum is S2. So we can write like S1+(S2)==target where S2 consists of all negative elements so its sum will be represented as:(-S2)
Hence S1+(-S2)=target.
Now if we divide the given array into two parts then we can see Sum of Part1+ Sum of Part2 == Sum of the array.
S1+S2=Sum
Hence on solving we get S1=(Sum+target)/2
So ultimately we want a subset S1 which has a sum equal to (Sum+target)/2
Now it got reduced to subset sum problem.
Here, in the end, we are multiplying with (int)Math.pow(2, count of zero in array) because here for 1 zero there will be two cases ie. +0 and -0 though the answer will be the same count will become twice.
So in end, we are multiplying with (int)Math. pow(2, count of zero).
It is an example of 01 Knapsack so we have a choice either to take an item or not. and if we take it then it should be full and not repeating.
That's why we have added case if sum<target return 0
and if sum< -target also then also return 0
it means we can not reach to target by all elements given. We should either have more elements in an array or repeat the elements present in the array. (Which is possible in an unbounded knapsack, not 01 knapsack) .
TIME:O(N*VAL)[LeetCode time: 12 ms faster than 64.61%]
SPACE:O(N*VAL)[LeetCode memory: 40.6Mb less than 11.95%]
This question is a classic example of counting the subsets with a given difference in the array.
Thanks for Reading.😇
Comments
Post a Comment