Welcome back.
Now in this video, let's try to think about how we can solve this question.
Now to summarize we will be given an array.
Let's say we are given the array one, two and three.
And we have to find all the subsets which are possible.
And we have seen that eight subsets are possible if the array which is given to us is of length three.
Now again, let me quickly write the possible subsets so I can have a subset which has zero elements.
So this is an empty array.
And then I can take one element.
So one two and three.
And I can take two elements one and two I could take one and three or I can take two and three.
And then I can take all the elements one two and three.
So these are the eight possible subsets.
Now why is this eight.
Let's try to think about the maths behind this.
Now when you look at these subsets right.
So again there is nothing over here.
When you look at these subsets you can see that in each of these either you include one or you don't
include one.
Right.
So there are two possibilities.
Either you include one or you don't include one.
Similarly about two.
Either you include two or you don't include two and about three.
Either you include three or you don't include three.
So that is what is happening when we are creating the subsets.
For example, in this case where we don't have anything, what is happening over here?
We are not including one, not including two and not including three.
So when we don't include anything, we get this empty array over here.
What about this one over here we are including one, not including two and not including three.
So that is how we are getting this over here for.
Let's take this one another example.
What about two comma three?
In this case we are not including one.
We are including two and we are including three.
So you can see that when we are forming each of these subsets, what we are doing is we are either including
that particular element or we are not including that particular element.
So for this element element one right.
For this element there are two possibilities which is include or don't include.
Similarly for this element over here there are two possibilities which is include or don't include.
And for this element over here.
Also there are two possibilities which is include or not include.
That's why when we take all the possibilities, that is the possibilities of element one.
I'm just calling this as element one.
So not to confuse when we talk about index and value just plain English, let's just try to understand
the logic.
When I talk about the possibilities for element one and the possibilities for element two and the possibilities
for element three, I have a total of two into two into two, which is equal to eight.
That's how I can say that if the array which is given to us has n elements, if it has n elements for
each of the elements, there are two possibilities which is either include or not include.
That's why the total number of subsets which we will get will be two into, two into two, etc. n times.
Which will be equal to two to the power n.
All right.
So this is an important concept right.
So it will help us understand this better.
So if we are given an array of size n then when we find the power set the power set will have two to
the power n elements.
And that's what we have seen over here.
This array over here had three elements.
And we have seen that the power set has two to the power three which is equal to eight elements over
here.
All right.
So I've just cleared up the board.
So we have seen that if we are given an array of length n then the power set will have two to the power
n elements.
Now let's proceed and look at how we can solve this question.
Again to summarize, the question was we will be given an array of size n and then we have to give as
the output an array which contains all these possible subsets, which is nothing but the power set.
All right.
Now we can solve this question in two possible ways.
One is doing it iteratively and the second way is doing recursively.
Now both these methods will have the same space and time complexity.
Now in this section, because we are discussing recursion, we will focus on the recursive solution
of this question now.
But just let's quickly discuss the logic about how we can solve this iteratively as well.
Now let's say we are given one, two, three.
This is the array which is given to us.
Now we start by building our power set.
And we have seen that always, no matter what the array which is given to us, there will be an array
which is empty as part of the power set.
Right.
So I've just included that initially itself in the output.
Now what we do is we take the first element which is one over here.
Now we are going to add that to all the elements which are already there.
So over here we just have this empty array.
So let's add one to that.
So I get an array which has just one as an element one over here.
So now we have two elements in our output array.
Now we go and take the next element which is two.
And we add that to the elements which are already there.
Which are these two over here.
Right.
So when I add two to the empty array over here, I get an array which has just two in it.
And when I add to the when I add two to this array over here, which has just one, I get this array
which has one and two.
Now we again do the same thing again.
We take the next element which is three, and we add it to the existing four elements.
Right.
So when when I add three to the empty array I get an array with only three.
Then when I add three to this array I get one comma three.
I add 3 to 2.
So I get two comma three and I add 3 to 1 comma two.
So I get one comma two comma three.
So this is how we can solve this iteratively.
Again we are not going to focus on this in this section because we are trying to deep dive into recursion.
So let's go ahead and discuss how we can solve this question recursively.
All right so for this let's take a sample input.
Let's say the input which is given to us is one comma eight comma seven.
All right.
Now to get to our solution, we start with an empty subset.
So this is our empty subset.
Now we have seen that for each of these elements what we can do is either we can include them or we
cannot include them.
Right.
Or we can say that we either add them to the subset over here or we don't add them.
All right.
So let's have a pointer.
Let's call it I.
And with this we will traverse the array which is given to us.
So we have I pointing to the zeroth index at this point.
Now our subset over here is empty.
Now we have two possibilities right.
We can either include one or we cannot include one.
Or we can add one or we can not add one.
So let's do that over here.
So in this case I don't add one.
And over here I add one to our subset over here.
Now we have this.
And what we what do we do.
We move I we move I to the next, uh element in the array which is eight over here.
All right.
Now for each of these possibilities I can either add eight or I can not add eight.
So let's do that.
So over here I don't add eight.
And in this case I add eight.
Now let me do the same thing over here I don't add eight.
And in that case I just have one and I add eight.
So I have one comma eight.
Again I move I to seven.
So I, I comes over here and for each of these four subsets I have the possibility of either not adding
seven or adding seven.
So let's do that.
So I have an empty array.
And then I have an array with only seven.
And in this case I have only eight or I have eight comma seven.
Over here I have only one or I have one comma seven.
And oh.
From over here I have one comma eight, or I have one comma eight comma seven.
And this gives us our output.
So I have to just take all these elements and push them to our output array.
And this is the results that we have.
Right.
So we have you can see we have eight elements over here.
And again we have discussed that because I have three uh the size of the array is three.
Right.
So that's why the power set has to have two to the power three which is equal to eight elements.
All right.
Now let's also try to this is basically an intuition.
This this is to help us develop an intuition of how we have to go about solving this question recursively.
Now let's look at the pseudocode.
And let's walk through this so that we can develop a better understanding.
And then we will go ahead and code this solution.
All right.
Now this is the pseudocode.
We will have a helper function.
All right.
So in the helper function we will check whether I we will pass an index to the helper function always.
And we will check whether I that particular index is equal to the length or n of the array which is
given to us.
And if it is equal then we will push it to the results array, which is what we have over here.
If it's not equal, we will go ahead.
If it's equal, we will push and then we will return.
Right.
So let me just write that over here.
But if it's not equal to the length then we will go through these steps.
So let's just take this example where we have the input array 187 and walk through it so that we can
understand it.
Now initially we will call this helper function and we will pass zero as the index and we will numb's
is the array which is given to us.
And then we will have an empty subset which is this one over here.
All right.
So we are over here now is I, I is equal to zero at this point which is passed to it.
So I is not equal to length which is three.
Right.
The length over here is three.
So what do we do.
We come over here.
Now we call the helper function again which is a recursive call.
And we increment I.
And again we pass numb's and we pass subset which is empty at this point.
Right.
And in that again we come over here.
Right.
So you can see that we are actually moving in this way.
Right.
So we have the initial call where I is equal to zero.
Then over here we incremented I and we made this call.
Right.
So we made this call that will again call the helper function I is not equal to three.
So we come again over here we increment I and we make this call right.
So we go ahead.
You can see that visually we go from here to here from here to here and from here to here when we have
this call finally I is equal to three.
Therefore we will push whatever is there in our subset to our results array.
And that's how we get this element over here in our results array.
All right.
So this part over here is done.
Now what do we do.
It returns.
So this this line is done for the call where we got I where I was equal to two and two plus one gave
us three.
So we came over here and we pushed this.
So this line is done.
Now what we do is we come to the next step which is pushing numb's at I so numb's at I at this point
I is equal to two, right.
So I is equal to two.
So we are making this call by pushing seven to the subset.
And then we are coming over here.
So num set I num set two at this point is seven because I is equal to two at that seven at that point.
Right I is equal to two.
So let me just write the indices zero one and two.
So we are pushing seven to the empty subset.
So this is how our subset looks like.
And then we are making this call helper I plus one.
So two plus one.
So two plus one is three right.
Two plus one is three.
And the subset at that point is.
An array with only seven.
So again we come over here, we see I is equal to three at that point because we are over here.
We did two plus one right.
So I is equal to three.
So at that point we are going to push this.
That is this array with only seven to our results array.
So that is this over here.
And that is how we are going to get seven in our results.
All right.
So this call is also done.
And after this we are just going to pop seven from the subset.
So we added seven over here.
And over here we are going to pop seven.
So seven is also removed from the subset.
And again our subset looks like this.
All right.
Now what do we do.
Again we move in this direction right.
We come over here.
And at this point when when we make this call we pass I as two.
Right.
Because we are increment at this point I is one.
We increment it.
So again all of this what we did was part of this call right.
This call.
So that is done.
So that was this.
So that is done.
So then we come over here we push num at I and I over here is equal to one.
So we push eight.
So this is how our subset looks like.
And then we call the helper function.
So again we come over here we see I is equal to two.
Over here it's not equal to three.
So we come over here we increment I and we again call the helper function which is this call.
And in this call we get eight added to the results array.
So after that we are done with this line of code.
Right.
Then we push numb's at two because I is over here.
Two right.
So that's seven.
So we push seven to the subset.
So the subset looks like this eight comma seven.
Again we increment I.
So that is this call over here right.
And I is equal to three.
Therefore we push eight comma seven to the our results array.
So in this manner you can see we are we are.
We initially had this added.
Then we had this added over here.
Then we have the array with eight added over here.
Then we have the array eight comma seven added over here.
So this is also done right.
So all of all of this is done.
This was part of this call.
Right.
Again it will return.
It will pop out seven.
It will return.
It will pop out eight.
And our subset again will look as an empty subset.
So you can notice over here that whenever we are adding something we are calling the helper function
recursively.
And then we are popping out or removing whatever we added.
So this is so that we can reuse the same subset array.
Whenever we are adding to the results.
We will make a copy using the dot slice operator, and we will make a copy and add it to the results
array over here.
But apart from that, whenever we are adding or removing something from the subset, we are using the
same subset array.
So that is why whatever was added over here is removed over here.
So you can see seven was added.
We remove it, eight was added, we remove it and we get back over here which is our empty subset.
All right.
Now let's proceed.
So we are done with these four elements.
Now again let me just remove this also so that it's easy for us to track what is happening.
All right.
Now, again, this was part of this call.
All of this, what we have done so far was part of this call.
Right?
And then we just made recursive calls.
We went in this direction, then we went over here, we went over here, we went over here, we went
over here and and over here.
But all of this was part of this call.
Right?
Again, that was a call over here where we call the helper function.
We incremented I and the subset was empty.
Now we are done with this because all of this is done and it has returned.
So this much is done and this line of code has executed.
Now we come over here right at this point I is equal to zero, right.
So we are going to push numb's at I, which is one to the subset.
And then we are going to make this call over here which is calling the helper function.
We are incrementing I.
So I is equal to one at this point.
Over here I is zero.
So I is one at this point.
And the subset looks like this.
So it's an array with only one right.
So again let me just wipe this.
So we are over here now.
As part of this call, we are going to recursively call again this where we increment I.
So I is equal to two.
Again we are going to call the helper function recursively and increment I where I is equal to three.
We are not adding anything to the subset right.
And that is how we will add this element to the results array.
And then after we are done with this we go in this direction.
At this point I is equal to two.
So we are going to add seven which is the element in the array at the index two.
Right.
So we are going to add seven to the subset and we will increment I.
So I is equal to three and we call the helper function.
So we pushed one comma seven to the results array.
So this is done.
This is done.
After this we added seven right.
So we are going to pop seven from the subset.
So we remove seven and we are done.
So this was part of the uh the call where we don't add anything from here.
Now that is done.
Now we are going to push numb's at I where I is equal to one.
So at index one we have element eight.
We are going to push eight to the subset in element I.
So I is equal to two and call the helper function again.
From there we are going to not add anything and increment I.
So I is equal to three.
So one comma eight is added to the results array.
We come back.
So this call is done.
And then we come over here we add seven.
So because I is equal to two right.
So at index two we have seven.
You can see we have seven.
So we add seven to our subset we increment I.
So I is equal to three.
And then we push one comma eight comma seven to our results array.
And this call is done.
We pop out seven.
We come back we pop out eight.
We come back and we pop out one.
And again our subset is empty.
So this is how this function works.
And you can see that recursively we were able to get the power set which is a set of eight elements
which is two to the power three.
Because the array which is given to us had three elements.