L11. Subset Sum II | Leetcode | Recursion

[@Vishalraj_1]

most of the time, I have solved questions by myself. But then also I watch your videos, Two reasons behind this is most of the time, I get to know more approaches to solve the question. and the second thing is how I can tell the solution to the interviewer. Yesterday was my interview and I tell brute then optimal approach with intuition(like you). And the interviewer was happy with my presentation. Thanks you making videos, it help me in both problem solving + presentation skills.

[@akmansr7149]

Hi, I am still unable to solve problems on my own. what should I do? 😥😥

[@omprakashhardaha7736]

@@akmansr7149 practice

[@akmansr7149]

@@omprakashhardaha7736 bhai doing that since a very long time. Seems like i suck. I can't solve problems without looking at discussion section or yt videos 😭

[@omprakashhardaha7736]

@@akmansr7149 bro i hv also same problem I suggest follow DSA kunal kushwaha course. You can start from recursion or binary search video.

[@shivansh2870]

@@akmansr7149same problem

[@CSBBADRIGAUTAM]

A huge thanks to you bro. This question helped get into job In my technical interview, I was to rate my coding skills and I said 8. He was supposed to ask the question of finding subsets of fixed size, and since I said my rating would be 8, he changed question to finding all subsets. I explained the code and everything. He was not believing my algo was correct. I guess What my interviewer was thinking to modify the original algo for prev question or something. He was saying I was wrong and I got worried a lot.😟😟 Then I shared my screen and drew the tree and explained everything as you did in this video (not as good as you though 😅😅) and he was *completely convinced* . He told me to move onto another question and he was still doubtful on the 1st question and did some research while I am doing my 2nd question (which is different question but same recursion application) and told me the solution for the first was the best optimal approach and got impressed a lot. 😂😂 A huge thanks to you bro.

[@abc-ym4zs]

in which software u have explained tree to the interviewer can u please tell if I encounter these type of persons it will be useful

[@CSBBADRIGAUTAM]

@@abc-ym4zs I didn't use any software, I just opened a document and explained using "/" and "\" as the links, wrting in next lines for children nodes or slashes (/ and \) and numbers in place of nodes. I used my mouse to show how each recursion goes for. It was online interview

[@akashsingh2722]

Damn!! congrats bhai

[@nimeshpareek953]

I was also asked this question once in an interview and I told the interviewer that we can solve this using recursion then he changed the question 😂😂

[@bruvhellnah]

​@@nimeshpareek953 what was the point of changing the question ? Are you not supposed to know the answer to what they ask lol Also what was the new question

[@adityarallapalli8308]

i != idx, instead of above condition, we can also write i > idx, which is intuitive.

[@HarshilAndhariya]

agree 🤝

[@takeUforward]

Please leave a small comment if you understand by spending your time here, every comment motivates me more :) C++ Code: github.com/striver79/SDESheet/blob/main/Subset-II_Cpp Java Code: github.com/striver79/SDESheet/blob/main/Subset-II_Java Instagram(For live sessions): instagram.com/striver_79/​

[@yuvrajluhach5665]

For Java code github link you have given C++ code , must be a mistake . 👍 Loving this series . I'm a 3rd year student any words of wisdom?😀 Like what should I not neglect whatever happens.

[@sheturaj7437]

One thing I did not understand is that aren't we generating wrong subsets if we are sorting the input array? For example:- if arr = [2,3,1,3,2], which after sorting would become [1,2,2,3,3], then won't [1,3,3] (and many more) which would be generated by your logic would be wrong since [3,1,3] would be the right subset?

[@-EE-AKASHJHA]

I have just solved 5 medium questions of leetcode having 10000+ likes in such a way that they don't feel even like easy problems, and when I used to see those questions earlier, I got fear and a question about whether I will be able to solve these questions ever but now I have not only solved them but understood the logic as well as written the pseudo code and also drawn the recursion tree. THANK YOU SO MUCH RAJ BHAIYA...

[@diyapathak2413]

pls tell me how b/c i feel so scared looking at them rn

[@RishabhSingh-xn3xu]

Everyone is Pro Until the new Question drops in the interview

[@codingwithsmallsteps2878]

Hi Striver. Thank you for the wonderful explanation of the Subsets II leetcode problem. I read the codes in discuss part for the problem but was unable to understand the logic behind it. But after watching your video, I have understood the logic and can write code for it.

[@anmolagarwal5600]

Alternative: when ignoring current element, also ignore all elements similar to current element. void help(vector& nums, int i, vector& s, vector temp){ if(i == nums.size()){ s.push_back(temp); return; } int j = i; while(j

[@anshumanpanigrahi7817]

I was having a doubt in this question, and I searched it on KZbin. Surprisingly, you solved this question before and I was delighted to know it from you.

[@aakritisingh399]

Indeed a great explanation, this problem has similarities to the combination sum-II problem. Enjoying the recursion series.

[@shiriii-x9h]

I never understood at which step to call recursion function and how exactly it gets implemented. But by watching your videos concepts goes so clear to mind, I gained a lot of confidence in those topics that I watched from your channel. Thanks for making great content.

[@jeremysilwoman]

another easy way i feel is using bits. say we have one 1, two 2 and one 3. So we can choose either one or zero 1s, two or one or zero 2s and one or zero 3s. so we can have an array to store count of each element. we start with {}. now we can either use one 1s or zero 1s. So {}, {1}. Now we can use zero/one/two 2s. So we have 2, 22, 222, 12, 122, 1222, 1, {}.similarly for next element.

[@rishabhkukreja6910]

Thanks a lot for the videos You are doing a great job Sometimes even if i have done the question before i still watch your video and i learn new ways to approach the same problem Great work !! Keep going !

[@pulkitjain5159]

following this series made so easy to do these problems of Subset1 and SubsetII as these follow the same concept of combination1 and Combination2 ,it is improving very much concepts of Recursion ,thanks for the awesome playlist sir

[@AdityaKumar-be7hx]

understood! The problem as well as the fact that I don't need to follow any one else for my algorithmic preparation. Keep up the great work!

[@Shivam-Varshney]

7:29.5 is important for understanding the indexing of the f(5,{3}) they took 5 as you have moved from 4th to the 5th index of this stuff .

[@TheNishant30]

this can also be solved with a modified take/not-take approach. it's just that when you are not taking an element, you dont only skip the current element, but also skip all its duplicates as well. essentially, you modify the recursive case to look for the next unique element. here's a pseudocode //BASE CASE if index > nums.length => push temp array's copy to result array => return //RECURSIVE CASE //all subsets that'll contain an element at a particular index => push nums[index] to the temp array =>call the function on (index+1) //all subsets that will NOT have an element at that particular index AND WILL NOT HAVE ITS DUPLICATES EITHER => pop the last element off your temp array => look for the next UNIQUE ELEMENT and call the function on that unique element's index. // here you dont only skip the element at index, but also index+1 if it's a duplicate, index+2 if it's also a duplicate..... so on and so forth, until you find the next unique element in the array. once you do, you call the function on that index. but what happens when there's no next unique element [1, 2, 2]? when you exclude 2 and look for the next UNIQUE element, will you find it? NO. what will you do then? not make a recursive call AT ALL? how will you reach the leaf node then? the base condition for that branch will not get satisfied and you will skip combinations that should have been there. HINT: IF THERE IS NO "NEXT" UNIQUE ELEMENT, CALL THE FUNCTION ON THE LAST DUPLICATE. let i = index+1 for(i; i < nums.length; i++) //Javascript folks, just use a var declaration here (-_-) { if (nums[i] == nums[index]){ continue; } else { break; } } => call the function and pass i as index for that call.

[@justkidding-h5y]

Watched ur previous videos on recursion and coded this one by myself....I am amazed I can finally solve recursion problems.... Thanks bhaiya for ur wonderful explanations😃

[@vedangfate6290]

Same here bro. The way he has simplified the whole process is so amazing

[@yuvrajluhach5665]

Combination II helped with this one , coded solution without referring video solution👍 developing the intuition

[@ashutoshthite]

that's true !

[@atharvakalele37]

the best channel for competitive programming! thanks a lot brother!

[@Shivam-Varshney]

25:02 if I!=Ind && nums[I] == num[i-1] continue and don't pick these conditions It means your I should be equal to index to be picked up in the call and if 2 successive indexes of array are same then don't pick up them in recursion call 🤙😎

[@iWontFakeIt]

ooooh! man, i solved this problem at first but i was wondering what went wrong as this problem is similar to combination sum problem, but finally i realised that i need to add all subsets into the final array. Hence i solved the problem and successfully understood the subtle difference between these two problems.

[@av21015]

Yeah me too faced the same issue . I didn't think there is no base case required.

[@shreyxnsh.14]

@@av21015 yeah, i was returning for the base case, thats why it wasnt working

[@Munchen888]

24:55 Can we use a condition “if i > idx …” It would be the same as in previous videos. Thus we don’t take the element we had seen.

[@joydeb8202]

Thanks a lot bhaiya... Abhi apka CP sheet kar raha... SDE Sheet iske baad🙌 Sukriya for all this help.❤️❤️

[@rohitsai9010]

Fantastic explanation.. U made recursion more easy and interesting.. Hats off your to patience

[@parthsalat]

C++ code starts at 25:30

[@tharungr7701]

simple as that, if array does not contains duplicates use pick and non pick method , if it has duplicate use for loop method :)

[@AlbertoRodriguez-oe6jo]

This is a backtracking problem, I mean recursion + backtracking, I thought I was missing something in the explanation but recognized it when I looked at the code.

[@anishkumargiri9490]

Efficient solution said by you is having the same time complexity as of brute force becuase in brute force it is going to take O(2^nlog2^n) and logbase2 to 2^n will be n so 2^n*n so what is the difference in time complexity between brute and efficient they are same.

[@bhaveshkumar6842]

This is the best placement series!!!!

[@CrazyHunk14]

able to solve this without seeing ur video!! cheers to your teaching method

[@Anonymous-q7t5c]

00:00 Solve subset sum2 problem with no duplicate subsets 04:06 Access all courses and get a free certification exam with subscription 08:25 Generating all unique size 2 lists from a given list. 12:16 Generate all sublists of given list 15:55 Generating unique subsets with recursion 19:42 Time and space complexity of recursive function 23:19 Generate subsets of a given array 26:51 Explanation of recursive code with data structure

[@SatyamKumar-bw4vi]

Hare Krishna! Great!

[@parthsalat]

Complexity analysis at 20:30

[@wisdomkhan]

this question is less of recursion but more in optimising the input and output

[@mukuldaftary9230]

Very Very Good Explanation , Very Helpful , keep on making these kind of videos.

[@neilmaheshwari9600]

Striver(bhaiya) i can't say aapki videos kitni helpful hai bs itna kahunga maine 5 6 alag alag logon ke recursion videos dekhe kabhi concept itna clear ni hua jitna aapse hua hai its a humble request aise hi guide karte rahiye and DP ki bhi series nikal dijiye...

[@sohamtanpathak9067]

Beautifully Explained!

[@vashishthsharma4411]

thank you bhaiya 😇😇😇😇

[@AtulKumar-c4x7l]

understood Thank you striver for such an amazing explanation..

[@saneetkaul8150]

Pro tip :- Watch and Solve Combination 1 and 2 in sheet before solving this

[@aishwaryas8283]

Thanks for the awesome explanation Striver. Can anyone help me understand why we are not using the pick and not-pick approach for the combination sum2 and subset sum2 problems? Didnt completely understand the reason for the differences in the approaches chosen.

[@venkateshvenky2880]

Understood clearly.

[@parthsalat]

Thanks for the amazing explanation!

[@akshitmangotra5370]

Thanks man! You make it so so so easy!

[@anshumaan1024]

C++ code at 25:30

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks striver for the video... :)

[@abhimanyu6534]

Great explanation But I think SDE sheet is getting difficult now 🥺😬😬

[@tekken1935]

Did u finish?. How is placement going?

[@abhayj8706]

@@tekken1935 i am in first year I am on dp

[@techbucks7339]

Been 2 years how you doing

[@gourabrajak8132]

u are the best striver,thnk u

[@shreyasingh1960]

I M ENJOYING THIS SERIES

[@pardhi8959]

hi man, thankyou for making video for us even if your not able to speak loud after tumor operation. ❤ love you bhaiya

[@kaichang8186]

understood, thanks for the perfect explanation

[@praveenkumarshah8581]

please use light color ink on dark background...

[@shitizgoel5027]

Thank you very much for this video Sir!

[@UECAshutoshKumar]

Thank you sir

[@Lalit_Shirsath]

for reducing time complexity ....can we use unordered set ? because all operations like insert will be O(1) ........ can we do that

[@rohandevaki4349]

pick and not pick is working with arralist contains method ,its time complexity is O(K), so total time complexity is (2*N *k),where k is the number of combinations

[@kunal4710]

//NOT OPTIMAL APPROACH AS WE ARE USING EXTRA SPACE AS SET FOR STORING ELEMENTS void solve(int i,vector& nums,vector temp,set< vector > &s){ if(i==nums.size()){ sort(temp.begin(),temp.end()); s.insert(temp); return; } //include temp.push_back(nums[i]); solve(i+1,nums,temp,s); temp.pop_back(); //Exclude solve(i+1,nums,temp,s); } vector subsetsWithDup(vector& nums) { vector ans; set< vector > s; vector temp; solve(0,nums,temp,s); for(auto it=s.begin();it!=s.end();it++){ ans.push_back(* it); } return ans; } SEE IT WORKS BUT IN THIS CASE YOU HAVE TO USE EXTRA SPACE HENCE NOT OPTIMAL

[@rohandevaki4349]

even the powerset method with bit manipulation without recursion works here, which time complexity is 2^n * n

[@hadiali5922]

We can even do it using find possible sub-arrays right? We can take a Hashset and we can simply store all the subarrays which are generated and HashSet will only take those subarrays which are unique in nature. Feel free to correct my approach .

[@yashjain93]

Set will take NLogN time to run n elements

[@ShubhamKumar-km8pm]

Thanks striver sir for explaning it the best way possible💯💯

[@rupamdwivedi9463]

THANK U SOOOO MUCH FOR WONDERFUL EXPLANATION

[@guptashashwat]

Acha samjhaya hai bhai!

[@nikunjgarg3754]

for brute force, i wrote this: class Solution { public: void uniqueSubsetHelper(int index, int n, vector &arr, set &ans, vector &temp) { if (index == n) { sort(temp.begin(), temp.end()); ans.insert(temp); return; } // pick temp.push_back(arr[index]); uniqueSubsetHelper(index+1, n, arr, ans, temp); // don't pick temp.pop_back(); uniqueSubsetHelper(index+1, n, arr, ans, temp); } vector subsetsWithDup(vector& nums) { set ans; vector temp; uniqueSubsetHelper(0, nums.size(), nums, ans, temp); vector finalAns; for (auto it = ans.begin(); it != ans.end(); it++) { finalAns.push_back( * it); } return finalAns; } }; but it isn't giving correct ans. Please help me someone.

[@abhishikthraj6921]

i think you are just using two recursive calls while there can be n of them so try using a loop as he explained

[@studynewthings1727]

I understood the video

[@dennyage4791]

but how' s the time complexity of converting hashset to List is ml* logm ?

[@rumiNITPatna]

thank you so much stiver !

[@tanmaysatsangi131]

plz anyone explain why the complexity of O(nlogn) to inset into set. OR I missed something at 2:22. Thanks in advance

[@venkatakasinathpeesapati3146]

Striver You are really Amazing..!

[@AkashKumar-lr6hc]

the best 30 minute

[@SuperWhatusername]

Thank you Striver

[@anubhavkalia5130]

Thanks Bhaiya

[@harshitverma2707]

Super easy thanks

[@apoorvgupta1211]

Hey Striver, Why do you use For loop in some solutions while not in others? When do we go for the For loop. I understand that this is just reducing effort of picking the element one at a time. Please let me know if i am wrong.

[@GhostVaibhav]

Understood 🔥

[@pavansai2859]

Thank you!!!

[@aryansonwani8145]

Thank you very much

[@bhagyashri7729]

if(i>ind) is easy to understand than (i != ind)

[@vaibhavsingh1282]

asking from the people who have cracked these interviews do u actually tell the interviewer the brute force and optimal approach of every problem or we can just tell them one approch

[@amandwivedi2302]

Using hashtable for the already visited will decrease the time complexity to ( 2**n +(n))

[@Rajesh-op8zx]

but will use extra space

[@sankalpjain4841]

Well Explained, Thanks ❤️

[@codemachine7381]

Absolute masterclass...

[@NazeerBashaShaik]

Understood, thank you.

[@aaryankedia3919]

Hey! Thank you such a clear explanation. I had a doubt, for the time complexity(TC), wont we add the time required for sorting the list?

[@Sarkar.editsz]

hands down , thanks a lot

[@dhanashreegodase4445]

I am not able to think this type of solutions by myself..🥺..I think I am doing copy and paste only that's the only waste of time

[@utkarshsharma6650]

try seeing any other tutorial, dont mug up the things

[@kunalverma9777]

void solve(vector& nums, int i, vector &ans , vector& v, int n){ if(i>=n){ ans.push_back(v); return; } v.push_back(nums[i]); solve(nums, i+1, ans, v, n); v.pop_back(); solve(nums, i+1, ans, v, n); } vector subsetsWithDup(vector& nums) { vector ans; sort(nums.begin(), nums.end()); vector v; solve(nums,0 ,ans, v, nums.size()); set s; for(int i=0; i this will help

[@nikitajaiswal9112]

Try aditya verma playlist for recursion you will be able to make solution by your own👍

[@nachosalo1793]

understood

[@GauravSharma-ij1ym]

Bruteforce approach TC should be 2^n * k*Logm where k is average sizE of subset and m(~2^n) is no. Of elements in the set . Why did u take 2^n * m*Logm. Subset size will not be 2^n. Can anyone explain?

[@rishikas8276]

I was trying to solve questions but for topics like recursion ,backtracking , graphs and stuff I’m not able to arrive at the solutions by myself ..I’m ending up referring to the solutions for most of questions like combinations , printing permutations etc Can you please tell me how to go about it so that I can come up with the solutions myself or if I’m doing something wrong Thanks!

[@kunal4710]

ALWAYS TRY TO DRAW RECURSION TREE OF WHATEVER CODE COMES TO YOUR MIND THEN ONLY YOU WILL GET TO KNOW WHERE YOU ARE WRONG

[@vasanthanv6143]

We are sorting the array, right? Why the time complexity for sorting the array is not taken into account? I know sorting is much better than storing the result into set and then converting into array List, but Arrays.sort() itself has some time complexity, right? Correct me if I am wrong.

[@harshitjaiswal9439]

understood.

[@ritiksahu5310]

i think we can do it with time complexity 2^N - approach sort the array into decreasing order (NlogN) process leave -pick 2^N gocha, final complexity, NlogN +2^N ~= 2^N

[@roct07]

This is so good

[@Sahilsharma-sk5vr]

LEETCODE 90. Subsets II Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. TEST CASE 15 - EXPECTED VALUE IS WRONG? Input nums = [4,4,4,1,4] Use Testcase MY Output [[],[1],[1,4],[4],[4,1],[4,1,4],[4,4],[4,4,1],[4,4,1,4],[4,4,4],[4,4,4,1],[4,4,4,1,4],[4,4,4,4]] Expected [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]] ^ ^ ^ | | |

[@surendrababu223]

Understood

[@saketmehta6697]

Will Interviewer be happy with that extra sort at starting? bcz that's again going to add nlogn time to our TC!

[@Metalrave]

an additional time of NlogN (due to sorting) would be very small (almost negligible) to the recusion's 2^n i.e exponential complexity.

[@satyamgupta6030]

thanks buddy

[@pulkitgupta669]

Understood Striver ❤❤

[@bsaikumarreddy1413]

Thanks for explanation bro. Change title of the video if possible

[@prashant7738]

[@sundarbsr4275]

understood ♥

[@aryansinha1818]

05:04