Welcome back.
So this is the code that we have just now written which is to find the power set of an array.
Now let's walk through the code.
And for this let's take the help of the diagram that we have previously drawn.
Right.
So this will help us to keep track of the recursions that's happening.
Now let's say we have passed in this array over here one eight and seven.
Now let's walk through the code with this.
Now we call the function.
And we pass this array over here.
So numb's is 187 over here.
And then we initialize output to be an empty array.
So let this be our empty array which is the output.
Now we come over here we have our helper function defined.
And then we come over here.
And the helper function is called.
We pass in the array 187 and the index zero is passed.
And then our subset at this point is an empty array.
So we come over here.
Now at this point I is equal to zero.
So I is not equal to numb's dot length which is three.
Right.
So the length over here is three.
So we come over here.
All right.
So this is the part where we are in this diagram.
And then we are going to call recursively the same helper function.
And we are passing the array 187.
And I at this point is equal to one.
And the subset at this point is empty.
So you can see that we came over here.
All right.
So at this point I is equal to one.
Now again we come to the helper function and I is equal to one.
At this point you can see we are over here and I is not equal to three.
So again we come to this part where again we call the helper function.
And I is incremented.
So I is equal to two.
So we can see that we come over here.
Right.
So I is equal to two at this point.
And again the subset is is the subset array is empty.
And we come and call the helper function again.
So we are over here again.
At this point I is equal to two.
So it's not equal to numb's dot length.
So we come over here and we call the helper function again with I is equal to three at this point which
is this over here.
So at this point I is equal to three.
All right.
So we are again over here.
Let me just clear this.
So that we can keep track of what's happening.
So we are over here I is equal to three.
And at this point we see that I is equal to numb's dot length which is three.
So we are going to push a copy of what is there in the subset which is an empty array.
Right.
So subset dot slice means we are making a copy of this and we are pushing it to the output array.
So let's write that over here.
So we are getting this copy over here.
And this is added to the output array.
Now we are going to return right.
So this call ends because we are returning over here.
So the help of function call over here is ended.
Now we come back.
So we are done with this call where I was equal to two.
Right.
So I was equal to two.
So two plus one gave us three.
And that was this call.
So that is over.
This is over now we come back.
Now what we are doing over here, we come to this line.
And at this point we are pushing Numb's at I and I is equal to two.
Right.
So this is zero, this is one, this is two.
So we are pushing seven to the subset.
So that is what we are getting over here.
And then we are calling the helper function.
So this is a helper function called where the subset is this array over here which has seven as an element.
And I at this point is two plus one which is three.
Right.
So we are coming again we are calling the helper function.
We are coming again over here.
And we see that I is equal to numb's dot length.
So we are going to push a copy of the subset which is this over here to the output array.
So we are getting seven over here.
And then we are returning.
So this call ends over here.
So we are done with this and we're done with pushing seven to the subset we call the helper function
with uh the subset having the element seven.
So that is also done.
Now we come out.
So because this returns over here right.
So we come back over here.
Now at this point we are going to pop seven.
So we added seven to the subset.
Now we're going to remove seven from the subset.
So again our subset at this point becomes an empty array.
So we are doing this because we are going to use the same subset array.
So we don't want to make copies right.
So when we push to the output array we make a copy.
But again throughout this we are going to use the same subset array.
So we are popping seven.
And this is how our subset looks at this point.
And we are done right.
So this part over here is done.
Now this was part of the call where again let me just clear this up so that we can keep track of it.
So we came to this part as part of this call.
Right.
So it came from I is I was equal to one, I was equal to one.
And one plus one gave us two.
So that is how we came over here.
Right.
So that is how we came over here.
And once we came over here we recursively call the helper function and came here and then here.
So this is done.
Now we come again over here.
So this part over here of this call right again we can we have to visually track this because this is
a recursive solution.
So to make it intuitive that's why I have this diagram over here.
So this part over here this call is done.
So this line over here is done.
Right now we are going to push Numb's at I.
And I at this point is equal to one.
So eight eight is pushed to the subset.
So our subset looks like this at this point.
And then we are going to have a helper function called right.
So again this is done this is done.
This this line over here was done.
So now we are having this call over here where the subset is an array with eight.
And I at this point is one.
So we are passing one plus one which is equal to two.
Right.
So we are coming again to the helper function because this is called now once we are over here we check
whether I is equal to three.
No I is equal to two at this point.
Right.
So we passed one plus one.
So I is equal to two.
So we come over here.
Now we are going to again call the helper function.
And we are passing this.
This is the subset at this point.
And I is going to be incremented.
So that is this call over here.
So we come over here I is equal to three.
Again we come over here we see I is equal to three.
So we push to the output array what we have over here.
So we get comma eight the array with only element eight over here.
So this call is also done because it returns over here.
So this is also done.
Now we are done with this call where I was equal to two.
Right.
So this is the call where I is equal to two.
And we did this call.
So this one over here that is completed.
So we come over here.
Now we are going to push to this numb's at I and I is equal to two.
So nums at I is seven.
So we are going to push seven to this array over here.
And we get eight comma seven.
And with this we are calling the helper function and incrementing I.
So I over here is three.
And this is how our subset looks like.
Again we come over here I is equal to numb's dot length at that point.
So we push eight comma seven the array eight comma seven to our output array and we return.
So this is also done now at this point this this this is this is completed right.
Its left and its right.
Or adding and not adding and adding is completed.
So we come over here and we pop.
Right.
So at this point uh, when we come out of this we just added seven.
So we pop seven.
So we remove seven from this.
Now when we come out of it we added eight.
So at this point we had added eight right.
So again over here we are going to remove eight also.
And we get back to this place.
So this is again how our subset looks like.
Let me just clear this so that we can keep track and we can continue tracing the algorithm.
All right.
So now we have completed this call.
Now what do we do after this?
Now over here.
It was part of this call, right?
All of this what we did was part of this call.
Right?
Which was when we passed the empty subset and I was equal to zero.
So we passed zero plus one.
So it was part of this call.
Whatever we did so far so and that part is completed.
So we come back to this.
Now we are going to push numb's at I and I is equal to zero.
So we are going to push one.
So we are going in this direction.
We are going to push and then we are going to make the helper call.
So this is this helper call.
All right.
So where the subset is uh an array with only one and I is incremented.
So I at this point becomes equal to one.
So zero plus one it's one.
So we we have this call.
So this part is completed.
So we have this call.
And as part of this call again we come to the helper function.
We move to the left right.
So we increment I and we don't add anything to it.
So that is this call.
And again as part of this call we come back to the helper function.
We again call it without with incrementing I and without adding anything which is this call at which
point later we have I is equal to three.
We push this over here and this call is done right.
Similarly, after that is done again we push numb's at I, which will be seven at that point because
I is equal to two when we are over here.
Right.
So we push two and then we make this call which adds one comma seven to our output array.
So this is also done when it returns.
And after it returns we are going to pop seven.
So we are going to remove seven.
And when we come back over here we have removed seven.
So this is how it looks like right.
So the left part this is done right.
This is done when I was equal to uh one right.
So one plus one gave us two and we had this call.
So now we are going to have the call where we add.
So at this point I is equal to one.
We are going to add eight.
We get one comma eight and I is equal to two.
At this point.
Again we go left.
So we add one comma eight.
And this call is done.
And we come back and we add seven.
So that also is added to the output array.
At this point we remove seven.
We come back over here we remove eight.
We come back over here.
And finally we remove one which is this over here when we had added.
So when this was adding one when we come back to that call.
Right.
So once that this call is completed we come back and we remove one also.
So we get our output over here.
And this is how this function works.
Now let's just summarize what is happening over here.
So we can see that if we trace the algorithm on a high level, what it is doing is first it comes over
here, then we recursively call it again.
We come over here.
At this point this is added.
Then we add seven.
Then we come back.
We add eight.
Then we print eight over here.
Then we add seven.
So you can see that this is how the algorithm works.
Then we go all the way up.
We go this way, we go this way and we go this way.
We have added it over here.
Then we add this one over here.
We come back, then we come over here and we come over here at that point, which we add the array one
comma eight.
And then we come over here and at this point we add one comma eight comma seven.
And that is how we are getting the output.
Now let's take a look at the space and time complexity.
We have already discussed that but let's just quickly take a relook at it.
Over here we can see that the input array had three elements at this point.
And the power set will have two to the power n elements right which is eight.
So we have we can see that there are eight elements over here.
So that is two to the power n.
Now for each of these for the the number of times we are pushing elements into these subsets can range
from zero.
At this point it's 0112, one, two, two and three.
So it's ranging from zero to 3 or 0 to n.
So on an average we are doing n by two times pushing to a subset.
So that's why we can say that the time complexity is of the order of two to the power n into n by two.
And again this is a constant.
So we can just avoid it.
That's why the time complexity of this algorithm is of the order of two to the power n into n, and
the space complexity is also of the order of two to the power n into n, because we can see that in
these subsets, right there are two to the power n subsets.
And on average we can say there are n by two elements per subset because it is ranging from zero to
n.
So again it's two to the power n into n by two.
And I'm just removing one by two because it's a constant.
So that's why the space complexity also of this solution is O of two to the power n into n.