9 Count of Subsets Sum with a Given Sum
ฝัง
- เผยแพร่เมื่อ 14 ต.ค. 2024
- Count of subsets sum with a Given sum
Given an array arr[] of length N and an integer X, the task is to find the number of subsets with sum equal to X.
Example:
Input: arr[] = {1, 2, 3, 3}, X = 6
Output: 3
All the possible subsets are {1, 2, 3},
{1, 2, 3} and {3, 3}
PROBLEM STATEMENT LINK:www.geeksforge....
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
bhai ek video pen ghumane par bhi bana dena
😂😂
@@TheAdityaVerma maine kosis ki bahot bar ghumane ki but failed :(
bhai uske liye jee ki coaching leni pdti hai...udhr seekh jate hain pen ghumana apne aap 🤣
@@amansharma7865 hahahha
@@TheAdityaVerma For every new DP problem first we should write recursive code and then convert it to bottom up approach ?
Engrave this in stones and history will witness that best ever tutorials created for Dynamic Programming on entire planet was created by Aditya Verma. Period.
Ok
striver better now
@@AniketSingh-nx4dsno
@@AniketSingh-nx4ds bhaiya abhi bhi aditya verma is best in terms of dp bhai
Everyone have different perspectives.
If it's not best then What's doing here Dude 😂
@@shivendrasingh8520
Thanks for this DP series Aditya! Great tutorial but I spotted one small potential mistake in the initialization part at 10:40. The problem is, that initializing the entire column with 1 will work only if the input array has all non-zero elements.
As me and a few others have pointed out, the method fails when the input array has any zeros.
For eg: n=3, sum=0.
We can have a set here as {0,1,2}, so there'll be subsets of {} and {0} possible hence count will be 2. This is true for multiple other input arrays where actually count >1 for sum=0, but we initialized count=1 for all input arrays when sum=0.
Here's a small fix I found to the issue:
We initialize the first column of the array acc to the formula: 2 ^ (no of zeros in the array at that size).
Hence, for eg: arr={0,0,1,0}, sum=0
For n=0, value will be 2^0 = 1, i.e {}
For n=1, value will be 2^1 = 2, i.e. {} and {0}
For n=2, value will be 2^2= 4, i.e. {}, {0}, {0} and {0,0}
For n=3, value will be 2^2 = 4, i.e. {}, {0], {0}, and {0,0}
For n=4, value will be 2^3 = 8 i.e. {}, .............., {0,0,0}
Reason:
In the sum of subset problem, we simply needed to return whether or not a set exists for sum=0, which was always True as empty set {} was always existing. Here, we need to return count of subsets for sum=0 (for first column), which will include all possible subsets in the array which add up to 0.
can you share the link of the code here? I am getting the wrong number of counts.
@@jyotijangid5243 Sure, it's in Python:
def find_zeros_in_array(arr):
return len([x for x in arr if x==0])
def count_of_subsets_with_given_sum_corrected(arr,n,W):
K = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for j in range(W+1):
if i==0 or j==0:
if i==0: K[i][j] = 0
if j==0: K[i][j] = 2**find_zeros_in_array(arr[:I])
#the only line that's different from the video
elif arr[i-1]
Thanks man for this observation
@@shadowofthecorpse9481 Thankyou
I think he mentioned it at 12:42 that this solution is only for the case when all the numbers are positive in the given array. Still great solution for the case of including a zero.
Definitely true when you said - "Yaar aisi problems krne mai kitna maza aara hai!!". Finally now my DP-phobia is going away and i am actually enjoying your videos!! Thank you bro :)
dp-phobia is real . repeat after me.
same here
@@samirpanday4898 sahi hai.....
hi, i am new here, he explains the concept, but what about coding? we have to do that ourselves? which language he uses in videos , c++ or java?
@@rishabhjoshi3092 hello, he just explains to generic code to solve the given problem. You can apply them any language. If you're using java you can replace some of the code with java methods. But the code he explains in any language Is more or less the same
9 of 50 (18%) done! I think need more explanation as to why we consider if (cur_elem
This lecture series is going into a hall of fame for all things algorithms. Watching your videos is synonymous with watching a movie. What a flow and what a way of presenting the information. Dude man you deserve to be a teacher of CS concepts, open an NGO bro or keep uploading such stuff. One word to sum it all #AMAZING!!!!!
I was literally waiting for something diff. but the next moment you said " HO GAYA BHAI"
I'll definitely share this channel of yours, because the explanation is just beyond amazing. Request you brother to keep making such videos.
hi, i am new here, he explains the concept, but what about coding? we have to do that ourselves? which language he uses in videos , c++ or java?😊
@@rishabhjoshi3092 My suggestion would be to pick Java or Cpp and try coding few problems initially and using standard libraries that provides data structures and algorithms. Once you code out a few problems. You'll get a hang of it and all you will then need is the logic which this guy is serving in an unmatchable way.
@@rishabhjoshi3092 c++
Awesome explanation.
Bhaiya you have only considered the case for positive elements.
If zero/es is/are also present in the array (as it is in gfg question), then we need to iterate:
for(int i=1;i 0) => dp[i][0] = dp[i-1][0]
else If(arr[i-1] dp[i][0] = dp[i-1][0] + dp[i-1][0]; and this extra term will lead to extra +1. And this extra +1 will exist whenever arr[i-1] == 0. Thus increasing our answers by
no. of zeroes whenever required.
Right in that case I think we can initialise it to number of zeroes as it will be equal to the number of subsets.
sir big fan
what is the value of 'm' here in
if(arr[i-1]>j) dp[i][j] = (dp[i-1][j])%m;
@@varshikjain1862 10^9 + 7
needs to be a pinned comment!
Me: "I'm not able to understand DP"
Professor: "You are dumb!!!"
Lee Aditya Verma: "Hold my beer🍺"
*aditya verma: hold my pen
@@tejasasthana6951 no hold my camera hoga agar pen de dega toh likhega kisse
while solving this problem on gfg you will encounter test cases where they have also included 0 in the array, so in order to tackle that scenario, only fill the first row for base case. Next start filling following rows using the technique of include/not include.
As for ex: if there is only 0 in array then as per base case the ans will be 1, however actually ans has to be 2: 1 empty subset and 1 subset with 0
can you provide solution as it still not working
thankyou for this comment and the explanation
@@harmansinghsaini9515 j ko zero se likho code likhthe time thats it
If 0 in the array then just reverse the array in descending order.
@@beingnitian2745 kaam ni kr raha hai
I have tried many DSA related videos but frankly speaking, you are the king of DSA for teaching the subject easily.
Because of you now DP or DSA looking like a piece of cake.!
I think in initialization we should only initialize the first row with 1 at (0, 0) and start second for loop with j = 0, because initializing the first column with all 1's might give the wrong result if there exists a 'zero' in the array.
Input for which this initialization do not work:
n = 10
sum = 31
9 7 0 3 9 8 6 5 7 6
Correct me if I am wrong.
correct
*Important point which is missed in the video*
int perfectSum(int arr[], int n, int sum)
{
// Using DP
int dp[n+1][sum+1];
int N = n+1;
int M=sum+1;
int mod=1e9 + 7;
//Initialization
for(int j =0; j
@@architarora-iiitd3265 Your argument is correct. but we don't need to initialize the array the way you said. Just initialise the first column with 1s. Then, just start the inner loop of j with j=0, as pointed out by some of the other comments. This will do the needful.
The values of the first column will automatically get updated as the iterations proceed. so there is no need to manually check the number of zeros.
@@hemang10 Yes, correct. I just wanted to highlight the point that what does initialising the first column to 1 denotes.
@@hemang10 Thankyou! Great explanation
17:18 !!!! Ultimate Swag !!!
For the 0 edge case in GFG, I found an alternate way to deal with it.
Ex: 2, 3, 0, 1
Our function calculates all possible calculations for elements before it.
This means possibilities are calculated only for 2,3 as they come before 0. Possibilites with 1 are left out and ans is lesser.
Hence if we shift all the 0's to the end we ensure to calculate all the possibilities. That is what i did.
Add this at the beginning
int[] temp_arr = new int[n];
int ind = 0;
// The problem came when 0's are dealt before other elements which
// meant that we calculated 0s permutations for a smaller subset
// meaning the answer would decrease
// By pushing 0's to the end, we ensure that the all permutations
// of 0's are calculated thus giving us the right answer
for(int i = 0; i < n; i++){
if(arr[i] != 0){
temp_arr[ind++] = arr[i];
}
}
for(int i = 0; i < n; i++){
arr[i] = temp_arr[i];
}
Also do modulo 1000000007 when you are calculating t[i][j].
📢📢Aditya's solution will fail for testcase that includes 0s in input array.
While initialization, in case of sum == 0, he is directly considering that only empty subset exists hence he is storing 1 in first column.
But consider, input arr= [0,0] and sum = 0.
here we CAN'T initialize first column with 1 since for sum = 0, subsets are {0(0th index)}, {0(1st index)}, {0,0} , {}. i.e. count 4.
The only change will be to use
if(sum == 0 && n == 0) then assign 1. (THIS CONDITION IS IMPORTANT)
if(n == 0) then assign 0
and rest will be handled by pick/no pick algo.
Thanks!! and overall great explanation by Aditya Verma💯💯
Thankyou so much!! It helped me:)
2 points i would like to add -
1-For those getting problem with multiple 0s, just start the column loop with j=0 instead of j=1 like this.
for(i=1;i
why we use t[i][j]= t[i-1][j-arr[i-1]] + t[i-1][j];
instead of t[i][j]= t[i][j-arr[i-1]] + t[i-1][j];
@@DeepakSoni-zq5rd bro i resembles N(number of items) , either we include the item or exclude, we have considered the item, so in every case i will decrease.
But marked t[0][0]=1.. Then only above code will work
why we getting error when using j=1 ?
@@atv8992 why j starts from 0 becoz in a given array we might have an element 0 which might gets missed out in case when j starts from 1
2 GODS who use DP
snax
Aditya verma
Underrated comment 😉
tushar roy
Bhai Aap OP biroooo.
snax kon hai??
@@prateekarora4549 pubg player hahaha
for reference see this i do this after watching this video
def path(arr,s,t,count=0):
if s
"Han bhai bs khatam hogya !!!" Apka ye line maja hi ajata h . Thank you so much Aditya , now I'm Loving DP!!!!!!
Hamesha shochta tha ki koi senior mentor mil jae. Aaj mil gaya bhai. Bhot shi videos h
I was looking for good DP series since last 1 year. Finally found this one. Best series ever. Can never thank you enough!
@Aditya Verma , Would you also upload a video where we are printing all these subsets as well .
using recursion would be better ig
static void findUniqueSubsets(int[] arr, int n, List temp) {
println("temp (to add)! " + temp);
//println("#" + list + "#");
if (n == arr.length) {
println(n + ":" + arr.length);
list.add(new ArrayList(temp));
println("#" + list + "added #");
}
println("#" + list + "#");
if (n < arr.length) {
temp.add(arr[n]);
println("temp after add " + temp);
findUniqueSubsets(arr, n + 1, temp);
temp.remove(temp.size() - 1);
println("temp after remove " + temp);
findUniqueSubsets(arr, n + 1, temp);
}
}
Really appreciate the level of mastery you have.. thumb rule yehi hai ki agar koi kisi aur ko concept samjha sakta hai toh his concepts are super strong, warna possible hi nahi hai.. baki log direct code likh dete hai pura ka pura phir walk through karenge.
doubt:
in case when zeroes are present in the set given, the entries in the zeroth column may change
for eg :
arr[]={0,0,11,1};
then extra subsets for sum=0 {0},{0,0},{} so 1 will not work.
for each zero there will be two possibilities so count extra_zero
& then add 2*extra_zero +t[n][W]
@@najimali32 I think there is no need. You can initialize dp[0][0]=1 and dp[0][1..sum]=0
Now you have only 1 row initialized. Now if you run the dp from i=1..n and j= *0* ..sum
So we run the j loop from 0..sum instead of 1..sum, it will count number of subsets for 0 too.
If you still don't understand *how* :
In first loop we are at _ element.(sum=0)
1 0 0 0 0 0 0 0 0 0
_
Now we apply the condition. if(0
For those who are wondering about why the problem is not being submitted on GFG. Here is the solution:-
int perfectSum(int arr[], int n, int sum)
{
int t[n+1][sum+1];
memset(t,0,sizeof(t));
int cnt=1;
t[0][0]=1;
for(int i=0;i
didnt quite get why its happening can you elaborate or explain with eg ?
@@abhayjoshi362 ,
The reason is when you have an array like 9 7 0 3 9 8 6 5 7 6, you have to consider 0 also as an option
to make the subset whose sum is 0, so just calculating the values for j=0 rather than just initializing it as 1.
While using index as j=1
0 TO 31--->
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 2 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 2 0 2 2 0 2 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 2 0 3 2 0 3 0 0 0 4 0 2 4 0 2 0 0 0 2 0 0 2 0 0 0
0 0 1 0 0 0 2 1 3 2 1 3 0 0 2 4 3 4 4 3 2 0 0 4 2 2 4 2 2 0 0
0 0 1 0 0 1 2 1 4 2 1 3 2 1 5 6 4 7 4 3 4 4 3 8 6 5 6 2 2 4 2
0 0 1 0 1 1 2 2 4 2 2 5 3 5 7 7 7 9 5 8 10 8 10 12 9 9 10 5 10 10 7
0 0 1 0 1 1 3 2 4 3 2 6 4 7 9 11 9 11 10 11 15 15 17 19 18 14 18 15 18 20 19
0 0 1 0 1 2 3 2 5 3 3 7 7 9 13 14 11 17 14 18 24 26 26 30 28 25 33 30 35 39 37
While using index as j=0
0 TO 31--->
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 2 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 2 0 2 2 0 2 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 2 0 4 2 0 4 0 0 0 4 0 2 4 0 2 0 0 0 2 0 0 2 0 0 0
0 0 2 0 0 0 2 2 4 2 2 4 0 0 2 4 4 4 4 4 2 0 0 4 2 2 4 2 2 0 0
0 0 2 0 0 2 2 2 6 2 2 4 2 2 6 6 6 8 4 4 4 4 4 8 6 6 6 2 2 4 2
0 0 2 0 2 2 2 4 6 2 4 6 4 8 8 8 10 10 6 10 10 10 12 12 10 10 10 6 10 10 8
0 0 2 0 2 2 4 4 6 4 4 8 6 10 12 14 12 14 12 14 18 18 20 22 20 16 20 16 20 22 20
0 0 2 0 2 4 4 4 8 4 6 10 10 14 18 18 16 22 18 24 30 32 32 36 32 30 38 34 40 44 40
thanks bro!
thanks bhai
public static int findWays(int nums[], int sum) {
int N = nums.length;
int[][] mat = new int[N+1][sum+1];
mat[0][0] = 1;
int mod= (int)1e9+7;
for(int i = 1; i < N+1; i++) {
for(int j = 0; j < sum+1; j++) {
if(nums[i-1] > j) {
mat[i][j] = mat[i-1][j];
} else {
mat[i][j] = (mat[i-1][j-nums[i-1]] + mat[i-1][j])%mod;
}
}
}
return mat[N][sum]%mod;
}
// there is some modification required in the aditya's code that is the number of subsets of sum == 0
// the subsets will be the 2^i where i is the number of zeroes present in array till a given index .
// you can also map the number of zeroes with the index this will reduce the complexity
int count_zeros_till_index(int arr[],int i)//returns the numberof zeros in array till index i
{
int count=0;
for(int j=0;j
exactly..........because element can also be zero........😁
I think we don't need to initialize the array the way you said. Just initialise the first column with 1s. Then, just start the inner loop of j with j=0, as you have done in your code. This will do the needful.
The values of the first column will automatically get updated as the iterations proceed. so there is no need to manually check the number of zeros.
@@hemang10 Yeah, Counting will increase TC. Instead this multiply by 2 to last index's element
constraint in a problem sum can't we 0 if u study problem carefully
We can use this same code for subsetSum problem as well
And if value of final grid(t [ n ] [ sum ]) is > 0 return true.
Yes, but that would be bad as it will take more memory(bool - 1 Byte, int - 4 Bytes).
True but overkilling..
Sir... Thanks for these video's. Your explanations are really good. I have one question. if we have a arr with zero's in it, for example arr = [0,0,0,0,0,0,0,0,1] and S = 1. The top-down approach gives me just 1, but the correct ans should be 256. How do we initialize the t when there are zero's in the array?
try arr = [1,0,0,0,0,0,0,0,0] and S = 1 you get 256
@@pratikkedar9979 no you're changing the question. Even I have the same doubt as jacob
@Jacob Abraham the reason you're getting the wrong answer is because when we initialize the 1st column, t[i][0], we put 1 in there because in 1st column sum = 0 and an empty array sums up to 0, right ?
But with zeroes, we can't put 1 in there. Because, consider this example:
{0,0,0}, sum = 0 (1st column).
Now, when i=0 (that is empty array.) then we put t[0][0] = 1. Makes sense.
Now, i=1, i.e., elements = {0} and sum =0. The answer here is not 1 now. It is 2 because:
{} -> empty subset sums up to 0. Good.
{0} -> this subset also sums up to 0.
Now, see i = 2 i.e. elements = {0,0}
{} -> sums up to 0
{0} -> sums up to 0
{0} -> sums up to 0
{0,0} -> sums up to 0.
Total 4!
So we have 2 zeroes in the array till index 'i', so value is 2^2 = 4
Finally, i=3, elements = {0,0,0} => 3 zeroes => 2^3 = 8 subsets possible.
Basically, for every index 'i' in column 0, you need to check the number of zeroes in arr[0...i-1] and then put the value 2^(number of zeroes in array till index 'i') in the cell.
This question assumes that array consists of only natural numbers, otherwise our Initialisation for first column would be wrong!!!!
@@harshittrehan6232 awesome explanation bro..
I think there is no need. You can initialize dp[0][0]=1 and dp[0][1..sum]=0
Now you have only 1 row initialized. Now if you run the dp from i=1..n and j=*0*..sum
If we run the j loop from 0..sum instead of 1..sum, it will count number of subsets for 0 too.
If you still don't understand *how*:
In first loop we are at _ element.(sum=0)
1 0 0 0 0 0 0 0 0 0
_
Now we apply the condition. if(0
Aditya...I had a query...cant we do this by same code as the equal partition sum....and at end traversing the T[0....n][sum] column and RETURNING NUMBER OF TRUE FOUND IN THAT COLUMN.....?..(btw loved ur videos
I can see the difference between just a tutor and developer + tutor, and you fall into 2nd category, it's really difficult to explain these concepts , but you did it very well
Make videos on graph , backtracking and window sliding please. I like your approach towards concepts..You will rock Big bro .
I have one doubt in this video, Before this video or before using '+' , I was able to think of the changes like instead of T/F, we use 0/1 but regarding '+', I am not able to understand completely how we have used '+' by replacing '||'. If anyone knows ,then let me know too.
I know what you are going through but I'll tell you to draw the matrix and fill it code wise, although aditya content is great, try pep coding's "Target sum subset" then perform the code on a paper, you will get a clear idea what's happening inside.
vishal vishwakarma in the subset problem aditya used t = t[i][j-wt[i-1]] || t[i-1][j]
But here he used t = t[i-1][j-wt[i-1]] + t[i-1][j]
t[i] / t[i-1] which one is corrrct we include the element in our set?
dekh bhai tu startting se 4th element pr hai or ab tu chahta hai no of ways ki subset sum given sum ke braber ho jaaye toh, vo tarike jnme is 4th element ko include krke given sum mil rha hai + vo tarike jinme is 4th element ko include na krke bhi sum mil jaa rha hai, vo total hoga
if u have solved this problem using recursion before so it will be easy to understand bcz in recursion we call function 2 times 1st time we dont add element and in 2nd function we add element so when the added sum becomes equal to desired sum we do count++,so basically we are adding the count of both function called.
@@hasansayeed2155 t[i-1] is the correct one, aditya did it wrong accidently. the explaination is that i = 1, represents wt[0], which makes it wt[i -1] to access each element of the given 1d array;
@Aditya Verma Firstly the video and approach is very good. I tried this approach but it was failing for test cases containing multiple 0s such as:
arr[]={0,0,1}
sum=1
Expected Output: 4
My Output: 1
Maybe I missed something, can you suggest me something?
P.S.: The testcase is present in leetcode targetsum problem as {0,0,0,0,0,0,0,0,1}, sum=1, correct ouput = 256, my output=1
Start second loop from 0.
int perfectSum(int arr[], int n, int sum)
{
int dp[n+1][sum+1];
for(int i=0;i
@@BiharCentralSchool It helped a lot ...Thanks!
I watched your video, tried the question on gfg, it got submitted.. I was happy..
Then I realized that I did a mistake, I came back to your video and corrected by mistake of forgetting to give it a LIKE.
You are awesome bhai..
agar array mai 0 bhi diya ho toh , sirf first row par hee lagana aisa 1 0 0 0 0 0 0 baaki ka leya loop hee chalana j=0 se chalega na ki 1 one se REASON ( agar array mai 0 bhi hai toh no of ways with sum=0 badh jayega {}, {0}, {0,0,0} isme jaise 3 ho gya
Bhai what a content you have created...hats off to you! For this particular question we could do it by having the same matrix as for subset sum right? and then count the number of Trues present in t[i][10] and that should give us count of subsets? Is my understanding correct here?
Just a tip starts top-down dp loop, for J = 0 to sum+1, to handle If there is some 0 in the given array
Thankyou so much for making these videos ......they have made me fall in love with DP ...........I love your way of teaching ..
Amazing explanation brother I never see this type of explanation in my coding history!
I just want to appreciate your hard work. Initially I was skeptic about your video . Then i was facing issue with solving problems. Then one Friend recommended me your videos. Rest i first watched your recursion playlist. And now I am watching this series. You are great man.
vai,plz make a playlist on "GRAPH THEORY".please vai
After we generate the dp or t matrix , if we count number of true at last column we can get the number of subset. Can we say that?
Brother, i can't tell you how much important this lectures of DP are for me. Thank You so Much..
Concept ki feel aa rahi hai bhai.
Thanks a lot.
20:31 apka aadesh sar aakhon par sir ji ..... Greatest Explanation.........
The way you find correlations between dp problems is amazing.
Could you please upload combinatorics problems . Worth watching ur videos. Its a very unique channel. Keep Going Bro !! . U earned a subscriber !!
Will try
Can you pls explain why did we start j loop from 0 instead of 1. Already we've initialised i=0 and j=0 sides of array to desired result. but why from 1 instead of 0
Ur teaching style is awesome & plz make video on "LIS" and "kadane" using Dp
one doubt for t[i][0] (when i != 0) )how do we kow that there is only one possible subset? What if the array is {0}, {0,1}, {0,3,4,6} etc. then there are two possible subsets, one is empty subset and the other is {0}... Please explain someone
And if my doubt is correct then we should initialize only first row and start j from 0 in main loop.
Great video! Is there a leetcode problem based on this concept?
Sach bta rha hu aisa content kahi nhi milega❤️. Really your way of teaching is awesome.🤩🤩🙌🙌🙌
Thanks a lot sir🙏🙏
True definition of Teacher, Aditya Sir, salute for your contribution. Apki wajah se aaj ham jaise log v aaj dynamic programming ko shi tarike se sikh rahe🙏❤️
If there is a number 0 in the array given initializatoin will be different for j = 0, as it will come 2 somewhere ?
See if there is 0 in the array, do the code for non zero elements..
And then multiply the answer by 2 as you will get one subset without taking 0 and other taking 0 both will give same results
@@Astagfirullah.. There is code in this comment section.
@NAJIM CHOUDHARY I think there is no need. You can initialize dp[0][0]=1 and dp[0][1..sum]=0
Now you have only 1 row initialized. Now if you run the dp from i=1..n and j= *0* ..sum
So we run the j loop from 0..sum instead of 1..sum, it will count number of subsets for 0 too.
If you still don't understand *how* :
In first loop we are at _ element.(sum=0)
1 0 0 0 0 0 0 0 0 0
_
Now we apply the condition. if(0
@@a.yashwanth this is the more efficient approach. Thanks.
I went with 2^num of 0's, but this is better.
His code won't work for test cases which contain 0, and so zeroes need to be tackled separately. First observe something
for the testcase n = 5 ; arr[ ] = {2, 3, 5, 0, 0} ; sum = 5
the output must be 8
ie: {2, 3}, {2, 3, 0}, {2, 3, 0}, {2, 3, 0, 0}, {5}, {5, 0}, {5, 0}, {5, 0, 0}
if we exclude the zeroes from our computation we get 2 subsets ie: {2, 3} and {5}
and combination of subsets of zeroes will be 4 ie: {}, {0}, {0}, {0, 0}
or using the number of subsets formula: 2^number_of_zeroes
therefore the and is = unique subsets (excluding zeroes) * 2^number_of_zeroes = 2 * 4 = 8
try more testcases for clarity
The way I did it was that I sorted the array in descending order then counted the number of zeroes (which are now at the end of the array). Then edited the size of the array from n to n - number_of_zeroes because we no longer want the zeroes to be considered. finally performed dp on the new array and returned dp[n][sum] * 2^number_of_zeroes.
CODE:
#define M 1000000007
#define ll long long
int perfectSum(int arr[], int n, int sum)
{
sort(arr, arr + n, greater()); // sort in descending order
int num_zeroes = 0, k = n - 1;
while(arr[k] == 0)
num_zeroes++, k--;
// we dont want the zeroes to be considered by the dp code,
// bcoz we will tackle them seperately. so n = n - num_zeroes
n = n - num_zeroes;
// dp array declaration
int** dp = new int*[n + 1];
for(int i = 0;i < n + 1; i++)
dp[i] = new int[sum + 1];
for(int i = 0; i < n + 1; i++){
for(int j = 0; j < sum + 1; j++){
if(j == 0)
dp[i][j] = 1;
else if(i == 0)
dp[i][j] = 0;
else if(arr[i - 1]
woah, this is actually useful, I was wondering why perfect Sum wasnt working until, I just happened to slip by this
Thank you.. Thank you so much for standing by someone like me who is almost into depression just to understand these topics. That thank you id from bottom of my heart 🥺
For these type of questions, the input array will only have positive integers right? Because if we add 0 or negative numbers to the array the approach will become very different.
True Bro, once we added 0 (I didn't try with negative number), the approach becomes different, I didn't notice that before, observed after a few days when I tried a variation of the above question, e.i. Target Sum problem on LeetCode.
For Example: For input arr:[0, 1, 0] and subsets: 1.
Above Approach will return 2, but that actual answer will be 4.
@@amit2197kumar int perfectSum(int arr[], int n, int sum)
{
int dp[n+1][sum+1];
for(int i=0;i
@@amit2197kumar can you tell me how to handle that case with memoisation cause we are taking j=0 in initialisation but what about memoisation?
need more explanation on why used +
did not understand the intuition behind it
I fell in love with DP because of you Thanks :)
Please bhai, Graphs pr bhi video bnao. Keep up the good work. Thank You :)
U win so many hearts....the reason for this is ur knowledge and helping nature..
Thanks bro!
Can't we also do it by taking a boolean 2d array, just like the subset sum, and count all T's in the last column, where sum = given sum?
Thoughts?
i did the same, but its not working, i dont know why any hints?
very interesting and learning sessions till now. Sir what if we need to return the subsets with given sum. how we can do that?
tell me ,if u got thAt
Can this count also be obtained by summing up values of last column of matrix obtained in subset sum problem?
Just run the subset sum problem and obtain the matrix having T/F values. At end of it, just sum the last column's values (i.e. Sum (1->n+1, w))
I think so. Since the last row stores boolean values for n elements and sum = 1,2,3.....,sum. So, if we count the number of T in the last subset problem, we will get the number of possible subsets
Is this problem can be done by recursion than after that we memoize it?
Sir!please make videos on backtracking as well ❤
Could someone advise me on whether I should learn dynamic programming from Striver or Aditya Verma? Which one is better?
learn form here and do questions from striver's dp sheet
Vai u're love.
BitManipulation ka vi video banao..
Especially the approach needs to be understood and u're just nailing it.
Thanks brother, next is binary search. I will consider making on Bit Manipulation.
Thanks for the advice.
@@TheAdityaVerma Bhaii please yaar bass itna bata sakte ho aap ki minimum path sum kis type ka dynamic problem Qn hai ??? Please iska reply zaroor karna yaaran
A wonderful course given freely by GOD of DP. Thanks very Much Sir for providing Amazing Content.
We must not initialize the first column with 1, because there can be a case when the array contains 0 , in that case the number of subsets will increase.
We must only initialize the first row with first 1 and rest 0
What if we are not allowed to reuse the numbers once used for a particular set?
it's kind of like leetcode 560 problem. but arr= [1,1,1] and k=2 , gives output 3 but there answer output is 2. what's wrong there , then? By the way, great video for Dp concept and thanks for sharing it free of cost !
bhai genius tu, What a simple way u are solving problem..
# Initialisation fix for presence of zero elements in the array
# with which subsets of different lengths can also be formed
zc = [0]
for i in range(1, len(a)+1):
if a[i-1] == 0: zc.append(zc[i-1]+1)
else: zc.append(zc[i-1])
for i in range(n+1):
for j in range(S+1):
if i == 0: T[i][j] = 0
if j == 0: T[i][j] = pow(2, zc[i])
Bhaiya it would be awesome if you could do a similar series on Divide and Conquer based questions :) Thanks for the help
Finally I reached a state at which I am able to do the question by my self.Thank youuu
Hi @aditya verma bhaiya will this approach works when difference=0 and sum of array is odd ? I'm getting wrong answer.
boolean wale se bhi kr skte h kya ise?? jab j==n pr 'T' hoga toh count++ kr denge aur usko 'F' kr denge.... Please reply
Your explanation - awesome :) Thanks a lot bro. Never thought DP can be that easy :D
Thanks a lot Aditya. I was looking for videos to help me understand how to think DP way..!!! You immensely helped me. :)
if the order of subsets mattered, what will be the approach to solve that prob?
@Aditya Verma
bhaiya aap na jo padhaya hai vo bhot op hai.
but aak question mai test case asa hai jis mai hum j == 0 ko 1 sa nhi kr sakta hai
like in array if we are given with element 0 then there will be two possibility for sum = 0.
first is null subset and other is that element 0 these both will give you sum = 0.
so we cann't put j == 0 simply 1 in dp array.
plz correct if I am wrong.
Really nice explanation , knapsacks by default caters to +ve numbers , any suggestions for arrays having -ve numbers or negative target
bro , can u how to print those subset ??
bhaiya what will be the base condition in recursion, if we comapare recurssion code with dp
Bhai... Agar sum negative hua aur array ke elements integers hue to...
Matrix ki size kya hogi...
Initialisation kaise hoga...??
I think we can also use the same dp table from subset sum and count the no. of true in last column.
no wrong approach for example consider {1,1,1,1} target =2;
acc to your logic anwer is 3 by counting true in last column but its actual answer is 6
@@ojasvichaudhary8724 2 is answer if unique subsets is asked...6 is answer if redundent subsets also counted
right appproach
Sir, please include in this series about the DP and bit masking , because it is very much needed to understand the bitmasking(another fearful topic), and better than u I think no one can teach bitmasking, So please include that also as soon as possible
Tbh, DP+Bitsmasking is quiet a difficult topic for interviews, and not asked much.
@@TheAdityaVerma recursion par bana dena bhai
@@TheAdityaVerma
can uh please tell me what is wrong with this code
int perfectSum(int arr[], int n, int sum)
{
const unsigned int M = 1000000007;
int output[n+1][sum+1];
for(int i=0;i
Should we bow!!
Yeah Aditya Bhaiya Is a King!!!!
Bhai u r really amazing 👌👌.itna acha kaun padhata hai... 🙏🙏
Amazing explanation brother. But Bhai same code nai chala, (in gfg), after searching here n there(took lot of time) found the reason.,(After Initialization , for loop (for sum) should start with 0, and not with 1). You could have mentioned this point as well in video.😊
best dp series.Period.
How does this work with duplicates? Eg what should be the output for [2,3,5,6,8,10,2] and sum 10?. The code outputs 6. Can a number be part of more than one subset?
you got correct answer, Think like if number appears 2 times then it can be used 2 times.
bhaiya iske variation pe bhi ek video please
count of mean of subset sum with a given sum
Input: arr[] = {1, 2, 3}, X = 2
Output: 3
All the possible subsets are {2},
{1, 2, 3} and {1, 3}
What if we keep the || (or condition as it is) condition same as subset sum and just check after this statement. if(dp[i][j]==1){count++;}. Will this logic work??
And the best channel to learn dynamic programming
If multiple 0's are present in the array, and we know by fact that we can array any amount of zero in any subset, We can simply count the number of zero's at the beginning, and exclude it from the array, and at the end we can multiple answer by pow(2, number of zeros), as for each zero we have an option of including it or not.
one catch if using memoization, if the input is int[] input = new int[]{0,0,0,0,1,0,0,0,0}; you will get 16 subset sum count, when the output should be 256. easy solution to this is just sort the input array.
During initialization, why will the entire first column of matrix be 1? When sum=0, and n=0,1,2,3.... won't there be possibilities of sets with zero in them?
For eg: n=3, sum=0:
We can have a set here as {0,1,2}, so there'll be sunsets of {} and {0} possible so count will be 2 right? Similarly count can be different for different sets and may not always be 1 for n>=1.
Please clarify
yes u r right
This is an edge case when 0s are present in input array. You just have to run the inner loop from 0 instead of 1. It'll then count the number of ways of sum =0 also.
@@manavmohata1240 no Manav, if we take all subset of an array, we also consider null subset also.
No brother, if we take all subset of an array, we also consider null subset also.
But if zeroes are present in the array then it will also increment the zero sum. Lets say that there is one zero. Then there are two ways of getting zero: null set and take the zero.