Hello all and welcome back.
So in this video let's continue our discussion.
And now do the question return subsequences which we discussed in the last video.
So pretty sure that you have tried it yourself.
If you are able to get the answer then you are doing pretty great.
If in case you face some problem then let us discuss and I'm pretty sure that all your problem will
be solved, right?
So let us now try to actually apply the recursion framework only every one.
So before running onto the solution or starting to code, I always suggest that please make sure that
you are able to break down your problem on what exactly you want.
Okay?
Now, the reason I am pushing a lot on these steps every time is when you will do the assignment, when
you will be giving any interview any way, or solving these questions.
This is how your approach should be.
Okay.
And the question which you want to discuss now they are actually at a little higher level okay.
So if you are understanding, if you follow the framework and your understanding is clear, then you
will not be facing so many problems.
Okay, great.
So we have already seen that if the input is ABC, if the input is ABC, then how the answer which I
am going to get is something like this.
Now I expect this answer to be in a list, something which we have already discussed in the last module,
where we did all indices of a number that we can print, we can return as a list, we can give a list
and get answer here.
Okay.
So all these things you will be able to code easily once you understand the basics.
Right.
Okay.
Now let me just follow the framework everyone and let us see.
I think the problem can be broken down into the very first thing, which you should actually understand
is that yes, the problem can be broken down into simple smaller problems, right?
How that can be broken down.
Let us see.
Let's say if I am given a, B, c as an input and I get out b c from here.
Okay.
Now if I ask recursion to give me all the subsequence of bk, then the subsequence is going to be something
like this b, c, b, c and empty list.
Right?
So this is an empty list.
Just taking a little space here.
Now my whole aim is to make sure that by using what I have.
So I have this a character with me, right?
And by what recursion have returned to me?
Can I somehow get my answer?
I feel that yes, you can get your answer and how you can do that.
See if you just attach a to each and every subsequence of BK, I think your answer will be there.
How I can do that?
Pay attention everyone.
See, what I am saying is if you are able to attach a in front of all the subsequences of b and c,
which recursion has returned, and you do not have to worry how recursion is going to return the answer.
That is something which we assume it is going to be a, b, a, c, a, b, c and empty string.
So if I do a plus empty string, it is going to be something like a only right.
So this and if you will see actually we have eight strings in front of us.
We have eight strings in front of us.
And these are the total.
All the subsequences of my a, b, c, right.
So I hope you are able to visualize now how I am able to break the problem and what exactly I am going
to do.
Again, this step is very, very important because now you can take a call that yes, this problem seems
to be one which can be solved using recursion.
Okay.
So let us move forward now.
First.
Now let us think of base case.
Base case in this particular problem I believe, can be that if my string is empty, if n is equals
to zero, then I can just return.
A list like this.
Right.
Which is having a empty set like empty subsequence okay.
So this is my base case everyone.
Because a empty string of length n is equals to zero, it is going to have one subsequence, which is
nothing but an empty string okay.
again, a little bit tricky, but these are the concepts of uh, combinatorics.
Normally, uh, the permutation and combination.
But I hope you are able to understand the same that a string with an empty which is having nothing is
having one subsequence, which is nothing.
Okay.
And you can also assume that everything is actually subsequence of itself ABC we have ABC as subsequence.
So on that note.
Also, if n is equal to zero, I can return this one subsequence which is empty string.
Okay.
So not n is not equal to zero.
Here that length of n is zero and this is empty.
Second is recursive call.
Now in this particular question I have to make sure that I make recursion call first because I will
be working on my answer.
Right.
There is no way I can work on the answer first and then call the recursion.
So that's why.
Okay, that's why I'm going to make the recursion call first.
Okay.
Just call on whatever the string you are getting and take a slice of that with first character missing
and ask the question to get all the permutations right.
So just ask recursion in, let us say a small list.
To get all permutations for you.
So get permutations.
And you should be good right?
And third is your work.
Now one thing which you are going to feel in questions going forward is that your work or calculation
is going to increase a lot, because these are a little bit tricky questions okay.
So the amount of work which you have to do actually might be increased.
But again the understanding is that if you are able to do your work properly, if you actually just
follow everything the way you have written, the way you have conceptualized, then everything is going
to be fine and you won't face any problem.
Okay.
So now let us do this.
I hope the understanding is properly clear.
So what I have to do if my S1 is equal to an empty string.
All I have to do is I have to create an empty list and I can just return.
Let me just create this empty list with an empty single character and I can return this.
Okay, so this is the base case.
Base case is taken care of.
Right?
Now next is.
See, this is returning me a list.
Right.
That's how I have defined the overall function here.
Right.
This is going to be returning me a list on the same understanding.
I can just ask recursion.
I can just ask recursion that hey, can you please return me all the subsequences of whatever I'm passing
you?
And recursion should be good to give you.
Now this is the step.
This is exactly the step where when your string was ABC and you know that you are passing BC here,
you have to assume that your small answer it will have b, c BC and an empty character.
Okay, so we will see about the sequence, but you have to actually assume now and we have now seen
a lot of examples of that, of how this assumption works, that you are getting this particular in your
small answer.
Now, with small answer.
Having all of these four subsequences, can you create your answer or not?
That is the whole thing now.
So pay attention everyone again.
Now what is going to happen?
This is the final answer which I am going to return.
And I do not have to go in depth or anything that I have already told you that this is something which
we do after writing the code.
Okay.
And that has fabulously served us till now.
We have been able to solve so many questions and while writing the code, we do not have to worry on
that.
Okay, cool.
Now, the very first thing, which I believe is because these four, these four were also part of my
A, B, c these four were part of my sub sequence okay, of a, b, c I should just add all four of
them in my answer, right?
Because they will be the part of my final answer.
So I can just extend and add small answer here okay.
Now what I have done here extend is some function which you have already seen.
So if I have to explain, you extend quickly.
What happens is that if, let's say your list is.
So let me quickly explain you about extend.
If your list L2 is one two, three and if you write L2, extend.
And let us say you pass four, five, six something like this, then each and every of these element
gets added to your L2 list.
That is what extend is.
If you will append it will get appended like this, which is not something which we want, right?
This is not something we want.
We want that every character.
And let me see if I can get the definition here.
So extend list by appending elements from the iterable.
So if you are providing an iterable and these are the things which we have already covered in the foundations
of Python.
Right?
In this particular course, only if you have a little idea, we will highly suggest to go and see that
once again, because these things are going to get used a lot going forward.
Okay.
So once I do this your L2 is going to be
123456 okay.
So I'm going to make it a lot easier for you so that each and every one of you are able to understand.
I will be getting something like this here.
I'm again not focusing a lot on the order.
As of now we will see the same as well.
We will be able to make an order.
That is not a problem.
We will be able to create a right order.
Okay, so this is the string which you have when you extend here.
Your answer is also having these strings.
Right.
So as of now your answer is now having this string.
Now the next thing which we actually saw, the next thing which we actually saw was I have to do something
through which I can take each and every element of my small answer and add a or the element which I
am keeping with myself in front of that, and the element which I am keeping with myself in front of
that.
And I think that is also pretty much easy thing to do.
We have now done this a lot of times.
So for I or I would say for each permutation in small answer, what I have to do is I can just append
s one of zero, which is my character.
Actually, let me just define it as my character as well so that it is a lot easier to understand.
I just have to append my character in front of each permutation.
And once I do this, once I do this, I will be having my answer.
Okay, so yeah, this is the code.
If the understanding is clear though, you will see the code is a lot easier, right?
The code is actually a lot easier.
Let me run it and we are able to get our answers.
Okay.
And we are able to get our answers.
Now let us try to understand this a little bit more deep, because the understanding is going to help
you a lot in future questions as well.
So pay attention again everyone.
What's going to happen?
I am calling my function with string ABC and asking it to get me all the subsequences right.
Subsequences we have discussed in length in the last video, so please make sure that you see that it
makes a recursive call.
It makes a recursive call on part of my string.
Then Now you can think of everything which is going to go down.
You have written your code.
I am very fine with that if you think of this now, because actually, if you will understand in your
interviews or your any competition, if you keep on doing this before writing the code, it is going
to take a lot of time, right?
So the approach which I tell works pretty well works pretty fine.
I have cleared number of ways, number of competitions and round using this particular approach only,
and it seems to serve me well every time.
Next is going to call on C.
And at each of these places this is the character we are keeping for ourself A, B and C.
Now next one is going to call for an empty string.
Now we know that this seems to be the base case, and it is going to return me a empty string like this.
Okay, with this empty string with me, what I have done is first I have extended.
So I am going to create another list here, which is going to be my answer of this function.
Answer of this function.
Let me call let me name this function answer to answer one, two and three.
So let me call it answer three.
Okay.
Just for the division.
And I am saying that hey, first in answer three, add whatever you are getting from from the function
call which is a small answer.
So this will be get added.
And then and then add my character in front of whatever you have got.
So this is going to be your answer three which is going to get returned to be now again here we will
create a answer two.
So let me make it here.
Answer two it is going to say the same thing.
Hey first add everything which you have returned, which you have got, and then add and then add B
in front of them.
Right.
So it has got a little bit messy, but it should be fine.
I hope you are able to catch it everyone.
Now let me actually make it to the some state that would be better one second.
So yeah I think this is a little bit clear.
Right.
Or let me try.
Uh, yeah okay.
Should be fine.
I think we can see it here only.
Right.
now, once I have gotten my answer to and which is, I'm going to return the answer one.
Okay.
It's also asking, hey, first add all of them.
First add all of them.
And here is something you will understand.
You will be able to make sense of order as well.
For example, I will see that because I am appending this first to my answer, the answer to which I
am getting what is going to happen here is that I will get these first in my answer as well, when I
will see that right.
So pay attention here everyone.
These are the first four strings, right?
Empty string c, b and bc.
Okay, so that's why I was saying that we will be able to make sense of order as well.
Now answer one.
Going to first add all these and then add a in front of them and add a in front of them.
So not writing that I am pretty sure that this is clear.
Now this is what you are going to see.
And now I hope you are able to see how the order is getting made.
Please try to make it yourself once because I want that all of you understand how this order is getting
made as well.
Okay, it is not that just it is not just that we are just seeing the answer.
We should be comfortable with the understanding and not just the answer.
Okay, let me learn it quickly for you.
So the last visualization.
Okay.
Now I'm doing all this because in the very first time it's going to help you a lot.
Okay, great.
So see everyone.
S1 a b c.
It's going to make a call to BK, then call to C and then call to A.
So sorry empty string.
Empty string.
Going to return the answer which is an empty list.
So let it return right.
It got the small answer is empty list.
And it's going to make its answer now.
So it's character is C.
It's going to create an empty list.
And it's going to add everything there.
Right.
So that's now the loop is going to run.
First we extend.
So whatever was there we are able to add.
Now we are adding C here.
The loop is finished.
We are going to return this answer.
And my BK one.
This returns of sequence function with S1 as BK is going to get the small answer as yes.
Now going forward everyone, my car is B answer is going to be an empty list.
Again, I'm going to first extend it.
And I've told you already extend.
Just add all the elements here.
So see it's got extended.
Then I'm going to do the same thing.
I'm going to add B in front of them.
So see first B gets added in front of this.
So it's a B only then it's get added in front of this.
So it's going to be BC right.
If you would have added this my character towards the end, then your string would have been made c
b which would have not been right.
Okay.
C b would not have been right because sequence is something which you have to maintain in such sequence
as well.
Now this is your small answer.
This is the final answer which you want to return.
And here was when I asked you to write the code like this is where you actually have to visualize and
write your code.
You have to assume that this is a small answer which you are going to get.
And now write your code.
And if you are writing your code properly, then this code is going to get toppled out to the recursion
and everything is going to work fine.
So this is the answer.
After extending and now I hope you understand how it's going to get added, just adding a in front of
them and finally going to return my answer.
So this is the return value.
And seeing like we have written a fabulous code for getting all the subsequences is going to work extremely
well.
It doesn't matter how long the string is.
Okay, so see everyone one second here.
Here we are able to get for four characters as well, right?
Just understand one thing as well.
If someone some interview asked you that hey I don't want it in this order.
You can just remove this and extend afterwards as well.
So these are small things which you will change in your code and see the answer and also draw everything
the way I have drawn.
You will be able to get hold of them.
Okay everyone.
So yeah with that I hope the question properly of getting and returning all the subsequences of a given
string is clear.
Please focus on the pattern.
Please focus on exactly what the problem is and how we are actually moving towards a solution, rather
than remembering the code, or just, I would say, solving it quickly.
Take your time.
Draw all the trees.
Draw all the function calls.
Make sure you are able to get the order right and then you will feel a lot more confident.
Okay, so cool everyone!
Now let's meet in the next class and solve more questions.
Thank you.