9 Count of Subsets Sum with a Given Sum
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.geeksforgeeks.org/count-o...
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.
Пікірлер: 866
bhai ek video pen ghumane par bhi bana dena
@TheAdityaVerma
4 жыл бұрын
😂😂
@svworld01
4 жыл бұрын
@@TheAdityaVerma maine kosis ki bahot bar ghumane ki but failed :(
@amansharma7865
4 жыл бұрын
bhai uske liye jee ki coaching leni pdti hai...udhr seekh jate hain pen ghumana apne aap 🤣
@nikhilnaidu1383
4 жыл бұрын
@@amansharma7865 hahahha
@amanwatts24
4 жыл бұрын
@@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.
@ytg6663
2 жыл бұрын
Ok
@AniketSingh-nx4ds
Жыл бұрын
striver better now
@anonymousanonymous7507
7 ай бұрын
@@AniketSingh-nx4dsno
@shivendrasingh8520
Ай бұрын
@@AniketSingh-nx4ds bhaiya abhi bhi aditya verma is best in terms of dp bhai
@30sunique78
19 күн бұрын
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.
@jyotijangid5243
4 жыл бұрын
can you share the link of the code here? I am getting the wrong number of counts.
@shadowofthecorpse9481
4 жыл бұрын
@@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]
@ravishekranjan7282
4 жыл бұрын
Thanks man for this observation
@jyotijangid5243
4 жыл бұрын
@@shadowofthecorpse9481 Thankyou
@ironmonk4074
4 жыл бұрын
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.
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"
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 :)
@samirpanday4898
3 жыл бұрын
dp-phobia is real . repeat after me.
@kaushalmzp
3 жыл бұрын
same here
@vibhu613
3 жыл бұрын
@@samirpanday4898 sahi hai.....
@rishabhjoshi3092
2 жыл бұрын
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?
@arfaatsyed6853
Жыл бұрын
@@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
I was looking for good DP series since last 1 year. Finally found this one. Best series ever. Can never thank you enough!
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.!
9 of 50 (18%) done! I think need more explanation as to why we consider if (cur_elem
Me: "I'm not able to understand DP" Professor: "You are dumb!!!" Lee Aditya Verma: "Hold my beer🍺"
@tejasasthana6951
2 жыл бұрын
*aditya verma: hold my pen
@AvikNayak_
2 жыл бұрын
@@tejasasthana6951 no hold my camera hoga agar pen de dega toh likhega kisse
I'll definitely share this channel of yours, because the explanation is just beyond amazing. Request you brother to keep making such videos.
@rishabhjoshi3092
2 жыл бұрын
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?😊
@akhiljain1695
2 жыл бұрын
@@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.
@mohit84604
Жыл бұрын
@@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.
@sarthakbhatia7639
2 жыл бұрын
Right in that case I think we can initialise it to number of zeroes as it will be equal to the number of subsets.
@yashrajpathak8103
2 жыл бұрын
sir big fan
@varshikjain1862
2 жыл бұрын
what is the value of 'm' here in if(arr[i-1]>j) dp[i][j] = (dp[i-1][j])%m;
@fardeenalam6929
2 жыл бұрын
@@varshikjain1862 10^9 + 7
@harshitewari
Ай бұрын
needs to be a pinned comment!
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🙏❤️
2 GODS who use DP snax Aditya verma
@smitchaudhari9783
3 жыл бұрын
Underrated comment 😉
@miteshbhuptani5542
3 жыл бұрын
tushar roy
@manikantareddy7595
3 жыл бұрын
Bhai Aap OP biroooo.
@prateekarora4549
3 жыл бұрын
snax kon hai??
@nikhilnaidu1383
3 жыл бұрын
@@prateekarora4549 pubg player hahaha
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.
Brother, i can't tell you how much important this lectures of DP are for me. Thank You so Much..
The way you find correlations between dp problems is amazing.
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
Thankyou so much for making these videos ......they have made me fall in love with DP ...........I love your way of teaching ..
Your explanation - awesome :) Thanks a lot bro. Never thought DP can be that easy :D
17:18 !!!! Ultimate Swag !!!
U win so many hearts....the reason for this is ur knowledge and helping nature.. Thanks bro!
Amazing explanation brother I never see this type of explanation in my coding history!
"Han bhai bs khatam hogya !!!" Apka ye line maja hi ajata h . Thank you so much Aditya , now I'm Loving DP!!!!!!
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.
Hamesha shochta tha ki koi senior mentor mil jae. Aaj mil gaya bhai. Bhot shi videos h
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 🥺
Thank you for the video, series. The concepts are lot clearer now :)
These videos are so good man! Thank you for providing it for free!
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
@abhayjoshi362
11 ай бұрын
didnt quite get why its happening can you elaborate or explain with eg ?
@shubhammahindru3563
10 ай бұрын
@@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
@namansharma8586
9 ай бұрын
thanks bro!
@saurabhsoni738
8 ай бұрын
thanks bhai
@amitkarn1888
6 ай бұрын
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 for(int j = 0; 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; }
Make videos on graph , backtracking and window sliding please. I like your approach towards concepts..You will rock Big bro .
A wonderful course given freely by GOD of DP. Thanks very Much Sir for providing Amazing Content.
📢📢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💯💯
@aarchigandhi6617
Жыл бұрын
Thankyou so much!! It helped me:)
DP looks very easy after Learning from u.Thanks bro.
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
@harmansinghsaini9515
Жыл бұрын
can you provide solution as it still not working
@sohanshrungare8930
Жыл бұрын
thankyou for this comment and the explanation
@beingnitian2745
Жыл бұрын
@@harmansinghsaini9515 j ko zero se likho code likhthe time thats it
@avinesh8350
Жыл бұрын
If 0 in the array then just reverse the array in descending order.
@surajkumar9756
Жыл бұрын
@@beingnitian2745 kaam ni kr raha hai
Finally I reached a state at which I am able to do the question by my self.Thank youuu
Thanks a lot Aditya. I was looking for videos to help me understand how to think DP way..!!! You immensely helped me. :)
Sach bta rha hu aisa content kahi nhi milega❤️. Really your way of teaching is awesome.🤩🤩🙌🙌🙌 Thanks a lot sir🙏🙏
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
@DeepakSoni-zq5rd
3 жыл бұрын
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];
@coldfinger3472
3 жыл бұрын
@@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.
@karanrocks4447
2 жыл бұрын
But marked t[0][0]=1.. Then only above code will work
@atv8992
2 жыл бұрын
why we getting error when using j=1 ?
@vibhugupta3331
2 жыл бұрын
@@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
Wonderful explanation. Thanks
Ur teaching style is awesome & plz make video on "LIS" and "kadane" using Dp
I fell in love with DP because of you Thanks :)
"Yaar aisi problems krne mai kitna maza aara hai!!", just awesome!
bhai genius tu, What a simple way u are solving problem..
Definitely the best dp explaination ever🔥👍
Thank you so much sir. loving this series so much now Dp is my new crush due to you.
Best DP course on internet!
Concept ki feel aa rahi hai bhai. Thanks a lot.
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.
@sigmarules7504
2 жыл бұрын
correct
@architarora-iiitd3265
2 жыл бұрын
*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
@hemang10
2 жыл бұрын
@@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.
@architarora-iiitd3265
2 жыл бұрын
@@hemang10 Yes, correct. I just wanted to highlight the point that what does initialising the first column to 1 denotes.
@stellararts9926
Жыл бұрын
@@hemang10 Thankyou! Great explanation
You Nailed it ,awesome
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..
very underrated youtube channel, this is best u can get .
Bhaiya it would be awesome if you could do a similar series on Divide and Conquer based questions :) Thanks for the help
Just amazing!
Nice explanation..!!
for reference see this i do this after watching this video def path(arr,s,t,count=0): if s
20:31 apka aadesh sar aakhon par sir ji ..... Greatest Explanation.........
And the best channel to learn dynamic programming
Thank you very much. You are a genius.
// 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
@hemankpandya989
2 жыл бұрын
exactly..........because element can also be zero........😁
@hemang10
2 жыл бұрын
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.
@WizBoyYt
Жыл бұрын
@@hemang10 Yeah, Counting will increase TC. Instead this multiply by 2 to last index's element
@user-jp9jd6el1f
7 ай бұрын
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.
@VishalSharma-hq5ti
4 жыл бұрын
Yes, but that would be bad as it will take more memory(bool - 1 Byte, int - 4 Bytes).
@devendrasingh4776
4 жыл бұрын
True but overkilling..
17:19 OOOO bhai, aise swap hote hai pen fingers k beech, Aditya Bhai OP🔥🔥🔥
Great Video Brother. Keep Growing.
Bhai u r really amazing 👌👌.itna acha kaun padhata hai... 🙏🙏
thanks.. very useful...
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.
@vishalvishwakarma8276
2 жыл бұрын
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.
@hasansayeed2155
2 жыл бұрын
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?
@akash-lz2dq
2 жыл бұрын
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
@shivamtiwari3672
2 жыл бұрын
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.
@vishalvishwakarma8276
2 жыл бұрын
@@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;
Man you make amazing content. Seekh liya bhai poora CS is youtube channel se :-)
Thanku sir ji😊 Please upload video course on recursion and backtracking. Please sir!
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))
@harsh_here
2 жыл бұрын
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
Nice video 👌👍 awesome!!
100x better than any paid course 🔥
Epic explanation....
Thanks a bunch✌
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 if(arr[i] != 0){ temp_arr[ind++] = arr[i]; } } for(int i = 0; i arr[i] = temp_arr[i]; } Also do modulo 1000000007 when you are calculating t[i][j].
Sir!please make videos on backtracking as well ❤
What if we are not allowed to reuse the numbers once used for a particular set?
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.
@najimali32
4 жыл бұрын
for each zero there will be two possibilities so count extra_zero & then add 2*extra_zero +t[n][W]
@a.yashwanth
3 жыл бұрын
@@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
Please bhai, Graphs pr bhi video bnao. Keep up the good work. Thank You :)
Great video! Is there a leetcode problem based on this concept?
best dp series.Period.
i too have a habit or rotating pen while im thinking, btw its amazing explaination sir
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
Bhai aapka knowledge toh kamaal ka hai bhai
It will me amazing if you show it practically...I mean implementation using java
vai,plz make a playlist on "GRAPH THEORY".please vai
Thank you very much.
Could you please upload combinatorics problems . Worth watching ur videos. Its a very unique channel. Keep Going Bro !! . U earned a subscriber !!
@TheAdityaVerma
4 жыл бұрын
Will try
very nicely explained ....but pls upload the code in GIT
Understood Thanks
if the order of subsets mattered, what will be the approach to solve that prob?
thank you bhai you explained 1000x better than my college teachers
Please make video series on graphs and trees as well.
@Aditya Verma , Would you also upload a video where we are printing all these subsets as well .
@gamerhu7462
3 жыл бұрын
using recursion would be better ig
@Kuriocity
3 жыл бұрын
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 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); } }
you r a legend, yaar matlab extra dimmag lag hi nahi raha ,just normal changes and everything is explained properly
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
thank you !!
You are a gem ❤️
i like ur approach broooooooooooooooo
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??
BTW great explanation but what if we count all the number of True in the column of (sum == given sum) last column would that will give us correct answer?