Transcript for:
Recursion and Subsequences

hey everyone welcome back to the channel i hope you guys are doing extremely well so in the previous video we did learn about multiple recursion calls so where is that specifically used now you'll find in recursion a lot of questions or internet programming a lot of questions which does involve this particular term which is known as subsequences now what is the definition of a subsequence a sequence uh i or i can say a contagious or a non-contagious sequence it can be a contiguous it can be a non-contagious sequence which follows the order this is very important which follows the order this is what we call as a subsequence a sub array is just contagious but a sub sequence can be contagious as well as non-contagious let's understand if i give you an array which is something like three one two okay this is an array of size three if i ask you subsequence i can say three is a subsequence i can say one is a subsequence i can say two is a subsequence i can say 3 1 is a subsequence i can say 1 2 is a subsequence i can also say 3 2 is a subsequence i can also say 3 1 2 is a subsequence i hope that makes sense this is a contiguous contagious contiguous contiguous contagious but over here three and two as a non-contiguous subsequence but still it's a subsequence three one two is a subsequence but at the same time i cannot say three to one to be a subsequence because it's not following the order you have to make sure it follows the order of the array the order of the array is three has to be before one one has to be before two this is the order of the array so please make sure like if you're taking three two three has to be before two in the array so order has to be maintained in order to call it as a subsequence now apart from three two everything other is a sub array so a sub array can be a subsequence remember this so all of these are subsequences and also we can call as an like nothing an empty set as a subsequence also because we are not picking up any elements from the array that can also be called as a subsequence so in total in total there are eight subsequences for this n equal to three size array and i want you to write a function which pins down all the subsequences now this can be uh done using a very very famous algorithm power set for which i've already made a video you should definitely check it out how to do it using powerset but over here since we are learning recursion we will not be doing that we will be learning the recursive way okay so let's first understand some pattern now the array was uh 3 1 2 and i say that 3 comma 2 is a subsequence now let's observe a pattern okay let's observe a part so the pattern is very simple there were three elements there were three elements and i say that three i've taken three i have not taken one and i've taken two so if i do a take and a non take on indexes this index i'm taking this index i'm not taking this index i'm taking and if i do this then this is 3 and this is 2 hence i can get this particular subsequence so that's the pattern for an example i say that okay how will you get this one comma two subsequence again very simple not take take and take correct if i ask you how will you get three comma one again very very simple take take not again if i ask you how will you get three one two very simple take take take again if i ask you how will you get null not take not take nothing so what i am observing is for every index i have a couple of options either i say that i'm gonna take it i'm not gonna take it so depending on this i will try to solve this problem okay so you've got the intuition now let's uh look at the code if specifically my task was to give you the intuition now let's uh look at the code and this structure of code that i'm going to write is gonna be significant in going forward like you will see all the problems being solved using this particular structure of code so you need to understand the structure of koda it's a pattern that you have to keep it in your head every day tell your anyways let's get started so we will always have an index remember this we will always have an index so by the way just assume the array to be three one two assume the array to be three one two with indexes indexed as zero one two so assume you have an index and we have a data structure it let's assume it's a list in java in c plus plus it's a vector okay so i've taken a array or list or whatever you wish to so what i'll say is okay i know i'll have to start from three i'll have to go to one i'll have to go to two correct so specifically i have to go till index two that's for sure i have to go till index two there is no way that i can avoid that so i can say my base cases if the index by chance is equal to equal to n or crosses n i'll stop or i'll print it rather i will print the array and i will return that's what my base case will be apart from the base case what will i say i'll be like okay please add in the array this particular guy array of index or i can say whatever list you are carrying or i can say whatever list you are carrying please dot add in java you can use add in c plus plus you can use pushback and vector dot add array of i correct next you will be like function index plus 1 comma this particular list that you're carrying and whenever you this requestion will go and will come back correct so whenever you uh come back you'll be like let's remove this particular guy let's remove this particular guy why are you removing i'll explain you don't worry don't worry about that next you will like let's go with the same list right this is what the code will look like and the structure has to be in your mind always okay this is the case of take this is the case of not take okay now let's understand how this code works using a main function so if i write a main function and i'm assuming you have the array as 3 1 2 rather and then you call this function with index 0 and uh empty array okay so what will happen is this function this function basically calls this particular guy if i just shrink it down this particular guy correct next whenever this guy is called the index value is zero this is an empty array right this line is no more not executed because n is apparently three because the size of the array is three next you say in the array add it so your array will now contain the first element which is three next you say let's call the function say calling the function stating index plus one which you are saying that okay what i've done is i've taken the zeroth index yes i've taken three let's move to the next index which is one and please pass on the array three so this this particular array remember this this particular array is the sub sequence that you're trying to form so we went to event over here right now again the if base case will not be executed and you will again say in three any please add is can you please add array of index of one thereby thereby this will make sure that the array is now three comma which whichever is at the index one which is one after that you'll be like let's do f of index plus one which is two comma with the array three comma one now this function call will go please please understand indeed next f 2 comma 3 comma 1 is the array the base case will again not be executed the base case will again not be executed what will be the next step i'll say again array 3 1 can you please add array of 2 which is this time this 2 so please add it so your array becomes 3 1 2 perfect let's so you have done for this let's call the next one index plus 1 is 3 with the array 3 1 2 perfect now this will call another recursion with f of 3 array as 3 1 2 correct now this time the base cases if index is greater than equal to n and it's true and it's true and you're like print the array print this particular guy so i can say if i if i'm maintaining an output screen yes if i'm maintaining an output screen for the first time i will get three one two printed correct now you'll be like okay you have printed now it's time to return so let's return you have returned now if you have returned time to understand your array is having three one two for the last index you decided that this two yes this two has to be picked but you still have an option where you say you did come up with three one what if i do not pick the last index then the subsequence will stay as three one because logically you came up with three one and you wanted to decide for the last index and i said okay please pick it so you got three one two and i can say please do not pick it so i'll get the subsequence three one so in this way you can get both the subsequences so over here since you have added since you have added two has been added right 2 has been added you need to remove it that's why we say 3 1 2 please please remove array of like whatever is it since it will be at the last index you can just remove the last index which is array of index two this is why you remove after removal the array again becomes three one back to the state it was back to the state it came it came as three one it is back to that state once it is back to the state you call the next index saying it's back to the state i'll decide for this index i'm not gonna pick anything so please go with three one had you not removed had you not removed then that would have been 3 1 2 and you'd have passed this which would have been wrong so this time you call this it goes f 3 3 1 and this time again the index greater than equal to three true print and return so this time the printing will go and return so that this time the printing will happen for three and one okay just remove this the printing will happen for three and one so i will be over and i'll go back and once this is over i can easily come back let's come back over here now when you're coming back you realize you went with three one and you decided for the last index now you are at a position where you have a three one right so you have a three one and you have done for this guy where you have set key one will be taken now i'll say let's remove this one thereby the array again becomes three what are the options whenever you're saying someone is coming up with three what are the options for this particular guy you said okay please take so you got three one now you'll say do not take so you'll get three and then you can go on designing so in this way yes in this way can i say i can easily do it so you'll remove and again you will call for f of two radha and he'll call on with only three so this time again the call will go to f of two with three and again the same task will happen for the second index because this time you're coming with three nothing and this time you will again do a take so three comma two will happen and you'll say not take so only three will happen so in this way every other sub sequence can be easily formed so i hope you have understood the entire concept how the first call goes then comes how this call goes and comes but the critical portion over here was to understand the remove i'll give you a classical example to remember this stuff now imagine uh this is the trial room of a shopping mall okay and you went in there now tell me one thing if you have taken couple of clothes assuming over here couple of clothes is nothing but i'm saying take or not think you've taken a couple of clocks whenever you're trying the first cloth where this in this case is like picking up the first item you will have to take out your current dress you'll take it off and you'll wear the new clothes correct in order to wear the next set of clothes you have to again take it off now if you don't take it off how will you wear but this is why if you have added it over here understand if you have added this guy so this guy has been added so in order to try non addition you have to remove this now that's why it will be removed that's the concept of non removal so in this way you can draw the entire stuff but i'll try to explain you this using a recursion tree because that is how we will be doing across so let's take the array as three comma one comma two okay so i've taken the array as three comma one comma two and this time let's take the recursion tree as f of zero and an empty data structure so initially at the zeroth index maybe like i can try that means i can pick up three so if you pick up three you'll move to the next index because for the zeroth index you have picked up so your data structure will only be containing three or you can say i will not pick up hence the data structure will be moving empty to the index one correct now over here whenever i say f of zero and f of one and f of one over here you need to understand this function call was made previously and then it came back so this three yes this three which is added has to be removed has to be removed and then this function call will be made you need to understand this is how this pans out to be so what i'll now do is i will super super quick uh draw the recursion tree so it's f of zero empty data structure you say pick so you'll be like f of one pick three you'll be like not pick like f one do not pick empty data structure you'll be like pick first index do not pick this first index f of two three of one this will be f of two three of zero nothing again you'll be like pick not pick this would be f of three three one two so whenever you reach the third index yes whenever you reach the third index this can be printed so i'm just marking it as green that means it is printed then you go back this time this recursion call will come which is f of three and i just have three one so this time this will be printed so let's mark it as green next you'll go back now you can see this entire recursion is over goes back comes over here f of 2 3 again couple of directions pick and non pick so f of 3 comma 3 two and f of three comma just a three so this will be again the stem printed goes back comes over here prints goes back goes back so i can say this entire left stuff is done where you have ended up printing three one two three one three two and three so four sub sequences have been printed and if you realize four subsequences were printed by taking the first element now the other four will be printed by not taking yes the other four will be printed by not taking so i can easily do it by not taking that'll be an empty one again you can decide to take the first index f of one comma that'll be one and again if you decide to not take it will be f of two comma not take again if you decide to take and to not take it'll be like f of 3 comma 1 2 and this will be f of 3 comma 1 so if i decide this is the next printing comes back goes next printing comes back comes back f2 so over here what can you do again you can decide to you can decide to pick and do not pick so if you decide to pick it'll be like f of three of two it'll be f of three of empty so this will be printed and then this will be printed so if you carefully observe the next set of elements were also printed which is one two one and a two and then empty so you also printed the next four so in this way you can easily print so if i just show you the entire recursion tree this is how it looks this is how the entire recursion tree looks quite simple and if you want the vertical order the function calls have been made yes this is how the function calls have been made but i still highly recommend you to go back and draw the recursion tree by yourself to understand it okay so quite simple quite simple so if i try to write it down in the code uh can i sell i'll be taking an array so i'll just take an array you can do it by yourself three one two and i'll keep the n as three okay and i'll say print f i've written a print function which will print all the subsequence starts with index 0 array and then so let's write the printf printf i can say index i can say okay i need a data structure to carry all the subsequence let's take a data structure to carry all the subsequence which is ds okay so probably i can just call the vector into ds and i can pass the ds over here that's the better one okay over here you can take vector it remember it has to be passed by reference so please please make sure you take as a reference anyway it's gonna be n okay perfect now can i say if at the moment it reaches n or like it'll always reach and because you're moving linearly can i print the data structure i can definitely print the data structure so please please print the data structure which is c out of id uh this and after that you can just give an angle just to make sure that this is not done okay and after that you can just do a return so this is how you print it now i'll say uh take all the condition take or pick the particular index into the subsequence correct i can say that so what i'll be like is okay if i'm taking it i'll say data structure to push back in java you can use arraylist and you can just given dot add pushback array of index okay so this is what i've done i've pushed back the rf index in order to remove it's very simple you say pop back that will be deleted and over here i can say that printf sorry extremely sorry printf index you have done for the current index you'll move to the next you'll take the ds you'll take the array and you'll take then and whenever you come back now it's time to try the not pick or not take condition where you say that this element is not added to your subsequence okay that's what you simply do now over here what will be the case oh yeah i can say the case will be very simple you'll be like print f you like print f index plus one the ds and the array and the end so if you just do this and uh probably if you just run this you will see all the guys getting printed over here see three one two three one three two one two one two and the empty one is getting printed over here so you can also uh like ds dot size if by chance the draw size is zero you can say it's a null one so you can also print the null something like this this will also make sure that the null is printed so if i'll keep this c the knowledge printed at the last because not take not take not take you can also do it in the reverse order yes you can also do it in the reverse order where you say that okay do not pick condition will be at the front you can also do it in this way using do not pick condition is at the front so we again run it this time it will be see first null came because not pick not pick condition was executed and then it printed that's your wish if you want to do the pick if you want to do the non pick then it's your wish okay now coming across to the time complexity what's the time complexity can i say for every index there are a couple of options valid for every index you're having a couple of options right so for every index if you're having a couple of options can i say like it's like 2 over here 2 over here 2 over here 2 over here 2 for every index you're having two options so the time complexity is definitely 2 to the power n no doubt in this right and into for every subsequence you're using a for loop to print it like it's generally not n but overall you can say it's taking a time of n to print so near about 2 and into n is the time complexity space complexity will be how much what's the auxiliary stack space so if you look at the recursion tree it's like going from zero to one to two so the maximum number of recursions that will wait are three if you carefully think not more than three recursion calls will be waiting in stack space at max three because the depth of the recursion is 3 so i can say the stack space is coming out to be weak of n because the depth of the recursion that we can have at maximum is n so i can say this is the time complexity and this becomes the space complexity as simple as that and do i need to explain you anything else i don't think so i think that that is pretty much it just make sure you remember this pick and not pick for every index you decide whether to pick and not pick since uh there are two to the power n sub sequences for a given length n size array uh thereby we got eight subsequences for the size three array so guys i hope you have understood this entire explanation this push back pop back up add delete remove everything just in case if you have understood every everything please please make sure you give a like to this video you can do that right and if you're new to this channel please please do consider subscribing and yeah with this i'll be wrapping up this video let's meet in the next one [Music] will find a bye-bye in