1
00:00:00,690 --> 00:00:01,800
Welcome back.

2
00:00:01,800 --> 00:00:06,390
Now in this video, let's try to think about how we can solve this question.

3
00:00:06,390 --> 00:00:08,760
Now to summarize we will be given an array.

4
00:00:08,760 --> 00:00:11,370
Let's say we are given the array one, two and three.

5
00:00:11,370 --> 00:00:14,610
And we have to find all the subsets which are possible.

6
00:00:14,610 --> 00:00:20,520
And we have seen that eight subsets are possible if the array which is given to us is of length three.

7
00:00:20,520 --> 00:00:26,070
Now again, let me quickly write the possible subsets so I can have a subset which has zero elements.

8
00:00:26,070 --> 00:00:27,330
So this is an empty array.

9
00:00:27,330 --> 00:00:29,460
And then I can take one element.

10
00:00:29,460 --> 00:00:31,560
So one two and three.

11
00:00:31,860 --> 00:00:38,550
And I can take two elements one and two I could take one and three or I can take two and three.

12
00:00:39,030 --> 00:00:41,700
And then I can take all the elements one two and three.

13
00:00:41,700 --> 00:00:44,160
So these are the eight possible subsets.

14
00:00:44,160 --> 00:00:45,660
Now why is this eight.

15
00:00:45,660 --> 00:00:48,540
Let's try to think about the maths behind this.

16
00:00:48,540 --> 00:00:50,610
Now when you look at these subsets right.

17
00:00:50,610 --> 00:00:52,050
So again there is nothing over here.

18
00:00:52,050 --> 00:00:58,020
When you look at these subsets you can see that in each of these either you include one or you don't

19
00:00:58,020 --> 00:00:58,650
include one.

20
00:00:58,650 --> 00:00:58,860
Right.

21
00:00:58,860 --> 00:01:00,270
So there are two possibilities.

22
00:01:00,270 --> 00:01:03,060
Either you include one or you don't include one.

23
00:01:03,060 --> 00:01:04,650
Similarly about two.

24
00:01:04,680 --> 00:01:08,580
Either you include two or you don't include two and about three.

25
00:01:08,580 --> 00:01:11,400
Either you include three or you don't include three.

26
00:01:11,400 --> 00:01:14,430
So that is what is happening when we are creating the subsets.

27
00:01:14,430 --> 00:01:18,390
For example, in this case where we don't have anything, what is happening over here?

28
00:01:18,390 --> 00:01:22,320
We are not including one, not including two and not including three.

29
00:01:22,320 --> 00:01:25,650
So when we don't include anything, we get this empty array over here.

30
00:01:25,650 --> 00:01:30,600
What about this one over here we are including one, not including two and not including three.

31
00:01:30,600 --> 00:01:32,820
So that is how we are getting this over here for.

32
00:01:32,820 --> 00:01:34,320
Let's take this one another example.

33
00:01:34,320 --> 00:01:35,640
What about two comma three?

34
00:01:35,640 --> 00:01:37,980
In this case we are not including one.

35
00:01:37,980 --> 00:01:40,350
We are including two and we are including three.

36
00:01:40,350 --> 00:01:46,020
So you can see that when we are forming each of these subsets, what we are doing is we are either including

37
00:01:46,020 --> 00:01:49,710
that particular element or we are not including that particular element.

38
00:01:49,710 --> 00:01:52,740
So for this element element one right.

39
00:01:52,740 --> 00:01:56,970
For this element there are two possibilities which is include or don't include.

40
00:01:56,970 --> 00:02:02,370
Similarly for this element over here there are two possibilities which is include or don't include.

41
00:02:02,370 --> 00:02:04,080
And for this element over here.

42
00:02:04,080 --> 00:02:07,860
Also there are two possibilities which is include or not include.

43
00:02:07,860 --> 00:02:14,100
That's why when we take all the possibilities, that is the possibilities of element one.

44
00:02:14,490 --> 00:02:16,020
I'm just calling this as element one.

45
00:02:16,020 --> 00:02:21,510
So not to confuse when we talk about index and value just plain English, let's just try to understand

46
00:02:21,510 --> 00:02:22,200
the logic.

47
00:02:22,200 --> 00:02:29,700
When I talk about the possibilities for element one and the possibilities for element two and the possibilities

48
00:02:29,700 --> 00:02:35,580
for element three, I have a total of two into two into two, which is equal to eight.

49
00:02:35,850 --> 00:02:42,420
That's how I can say that if the array which is given to us has n elements, if it has n elements for

50
00:02:42,420 --> 00:02:46,770
each of the elements, there are two possibilities which is either include or not include.

51
00:02:46,770 --> 00:02:54,000
That's why the total number of subsets which we will get will be two into, two into two, etc. n times.

52
00:02:54,940 --> 00:02:57,280
Which will be equal to two to the power n.

53
00:02:57,310 --> 00:02:57,910
All right.

54
00:02:57,910 --> 00:02:59,920
So this is an important concept right.

55
00:02:59,920 --> 00:03:01,600
So it will help us understand this better.

56
00:03:01,600 --> 00:03:09,250
So if we are given an array of size n then when we find the power set the power set will have two to

57
00:03:09,250 --> 00:03:10,600
the power n elements.

58
00:03:10,600 --> 00:03:12,040
And that's what we have seen over here.

59
00:03:12,040 --> 00:03:13,660
This array over here had three elements.

60
00:03:13,660 --> 00:03:18,790
And we have seen that the power set has two to the power three which is equal to eight elements over

61
00:03:18,790 --> 00:03:19,180
here.

62
00:03:20,110 --> 00:03:20,530
All right.

63
00:03:20,530 --> 00:03:22,360
So I've just cleared up the board.

64
00:03:22,360 --> 00:03:28,900
So we have seen that if we are given an array of length n then the power set will have two to the power

65
00:03:28,900 --> 00:03:29,740
n elements.

66
00:03:29,770 --> 00:03:33,460
Now let's proceed and look at how we can solve this question.

67
00:03:33,490 --> 00:03:39,820
Again to summarize, the question was we will be given an array of size n and then we have to give as

68
00:03:39,820 --> 00:03:45,190
the output an array which contains all these possible subsets, which is nothing but the power set.

69
00:03:45,190 --> 00:03:45,670
All right.

70
00:03:45,700 --> 00:03:48,670
Now we can solve this question in two possible ways.

71
00:03:48,670 --> 00:03:52,180
One is doing it iteratively and the second way is doing recursively.

72
00:03:52,210 --> 00:03:56,320
Now both these methods will have the same space and time complexity.

73
00:03:56,350 --> 00:04:02,050
Now in this section, because we are discussing recursion, we will focus on the recursive solution

74
00:04:02,050 --> 00:04:03,400
of this question now.

75
00:04:03,400 --> 00:04:08,380
But just let's quickly discuss the logic about how we can solve this iteratively as well.

76
00:04:08,380 --> 00:04:10,600
Now let's say we are given one, two, three.

77
00:04:10,600 --> 00:04:12,280
This is the array which is given to us.

78
00:04:12,280 --> 00:04:15,040
Now we start by building our power set.

79
00:04:15,040 --> 00:04:20,590
And we have seen that always, no matter what the array which is given to us, there will be an array

80
00:04:20,590 --> 00:04:22,600
which is empty as part of the power set.

81
00:04:22,600 --> 00:04:22,900
Right.

82
00:04:22,900 --> 00:04:25,960
So I've just included that initially itself in the output.

83
00:04:25,960 --> 00:04:29,350
Now what we do is we take the first element which is one over here.

84
00:04:29,350 --> 00:04:32,620
Now we are going to add that to all the elements which are already there.

85
00:04:32,620 --> 00:04:35,080
So over here we just have this empty array.

86
00:04:35,080 --> 00:04:36,580
So let's add one to that.

87
00:04:36,580 --> 00:04:40,840
So I get an array which has just one as an element one over here.

88
00:04:40,840 --> 00:04:43,150
So now we have two elements in our output array.

89
00:04:43,150 --> 00:04:45,700
Now we go and take the next element which is two.

90
00:04:45,700 --> 00:04:48,640
And we add that to the elements which are already there.

91
00:04:48,640 --> 00:04:49,780
Which are these two over here.

92
00:04:49,780 --> 00:04:50,050
Right.

93
00:04:50,050 --> 00:04:54,700
So when I add two to the empty array over here, I get an array which has just two in it.

94
00:04:54,700 --> 00:05:00,250
And when I add to the when I add two to this array over here, which has just one, I get this array

95
00:05:00,250 --> 00:05:01,480
which has one and two.

96
00:05:01,510 --> 00:05:03,400
Now we again do the same thing again.

97
00:05:03,400 --> 00:05:07,570
We take the next element which is three, and we add it to the existing four elements.

98
00:05:07,570 --> 00:05:07,900
Right.

99
00:05:07,900 --> 00:05:12,520
So when when I add three to the empty array I get an array with only three.

100
00:05:13,000 --> 00:05:15,850
Then when I add three to this array I get one comma three.

101
00:05:15,850 --> 00:05:17,140
I add 3 to 2.

102
00:05:17,170 --> 00:05:20,200
So I get two comma three and I add 3 to 1 comma two.

103
00:05:20,200 --> 00:05:21,880
So I get one comma two comma three.

104
00:05:21,880 --> 00:05:24,430
So this is how we can solve this iteratively.

105
00:05:24,430 --> 00:05:30,820
Again we are not going to focus on this in this section because we are trying to deep dive into recursion.

106
00:05:30,820 --> 00:05:35,440
So let's go ahead and discuss how we can solve this question recursively.

107
00:05:35,440 --> 00:05:38,290
All right so for this let's take a sample input.

108
00:05:38,290 --> 00:05:42,010
Let's say the input which is given to us is one comma eight comma seven.

109
00:05:43,300 --> 00:05:43,750
All right.

110
00:05:43,750 --> 00:05:48,340
Now to get to our solution, we start with an empty subset.

111
00:05:48,340 --> 00:05:49,900
So this is our empty subset.

112
00:05:49,930 --> 00:05:55,150
Now we have seen that for each of these elements what we can do is either we can include them or we

113
00:05:55,150 --> 00:05:56,050
cannot include them.

114
00:05:56,050 --> 00:05:56,380
Right.

115
00:05:56,380 --> 00:06:01,000
Or we can say that we either add them to the subset over here or we don't add them.

116
00:06:01,000 --> 00:06:01,360
All right.

117
00:06:01,360 --> 00:06:03,220
So let's have a pointer.

118
00:06:03,220 --> 00:06:04,120
Let's call it I.

119
00:06:04,120 --> 00:06:07,000
And with this we will traverse the array which is given to us.

120
00:06:07,000 --> 00:06:10,480
So we have I pointing to the zeroth index at this point.

121
00:06:10,480 --> 00:06:12,940
Now our subset over here is empty.

122
00:06:12,970 --> 00:06:14,620
Now we have two possibilities right.

123
00:06:14,620 --> 00:06:17,500
We can either include one or we cannot include one.

124
00:06:17,500 --> 00:06:20,200
Or we can add one or we can not add one.

125
00:06:20,200 --> 00:06:21,280
So let's do that over here.

126
00:06:21,280 --> 00:06:24,220
So in this case I don't add one.

127
00:06:24,220 --> 00:06:27,040
And over here I add one to our subset over here.

128
00:06:27,040 --> 00:06:28,600
Now we have this.

129
00:06:28,600 --> 00:06:29,920
And what we what do we do.

130
00:06:29,920 --> 00:06:35,110
We move I we move I to the next, uh element in the array which is eight over here.

131
00:06:35,440 --> 00:06:35,860
All right.

132
00:06:35,890 --> 00:06:41,830
Now for each of these possibilities I can either add eight or I can not add eight.

133
00:06:41,830 --> 00:06:42,790
So let's do that.

134
00:06:42,790 --> 00:06:45,070
So over here I don't add eight.

135
00:06:45,070 --> 00:06:46,780
And in this case I add eight.

136
00:06:46,780 --> 00:06:50,740
Now let me do the same thing over here I don't add eight.

137
00:06:50,740 --> 00:06:53,800
And in that case I just have one and I add eight.

138
00:06:53,800 --> 00:06:55,150
So I have one comma eight.

139
00:06:55,150 --> 00:06:56,830
Again I move I to seven.

140
00:06:56,830 --> 00:07:04,690
So I, I comes over here and for each of these four subsets I have the possibility of either not adding

141
00:07:04,690 --> 00:07:05,890
seven or adding seven.

142
00:07:05,890 --> 00:07:06,610
So let's do that.

143
00:07:06,610 --> 00:07:08,110
So I have an empty array.

144
00:07:08,110 --> 00:07:10,180
And then I have an array with only seven.

145
00:07:10,180 --> 00:07:14,320
And in this case I have only eight or I have eight comma seven.

146
00:07:14,320 --> 00:07:17,590
Over here I have only one or I have one comma seven.

147
00:07:17,590 --> 00:07:18,190
And oh.

148
00:07:18,190 --> 00:07:23,290
From over here I have one comma eight, or I have one comma eight comma seven.

149
00:07:23,290 --> 00:07:25,120
And this gives us our output.

150
00:07:25,120 --> 00:07:28,930
So I have to just take all these elements and push them to our output array.

151
00:07:28,930 --> 00:07:30,880
And this is the results that we have.

152
00:07:30,880 --> 00:07:31,060
Right.

153
00:07:31,060 --> 00:07:33,820
So we have you can see we have eight elements over here.

154
00:07:33,820 --> 00:07:37,960
And again we have discussed that because I have three uh the size of the array is three.

155
00:07:37,960 --> 00:07:38,230
Right.

156
00:07:38,230 --> 00:07:43,510
So that's why the power set has to have two to the power three which is equal to eight elements.

157
00:07:43,510 --> 00:07:44,170
All right.

158
00:07:44,170 --> 00:07:48,190
Now let's also try to this is basically an intuition.

159
00:07:48,190 --> 00:07:54,640
This this is to help us develop an intuition of how we have to go about solving this question recursively.

160
00:07:54,640 --> 00:07:56,710
Now let's look at the pseudocode.

161
00:07:56,710 --> 00:08:00,580
And let's walk through this so that we can develop a better understanding.

162
00:08:00,580 --> 00:08:03,250
And then we will go ahead and code this solution.

163
00:08:03,250 --> 00:08:03,760
All right.

164
00:08:03,790 --> 00:08:05,020
Now this is the pseudocode.

165
00:08:05,020 --> 00:08:06,280
We will have a helper function.

166
00:08:06,280 --> 00:08:06,670
All right.

167
00:08:06,670 --> 00:08:11,920
So in the helper function we will check whether I we will pass an index to the helper function always.

168
00:08:11,920 --> 00:08:17,860
And we will check whether I that particular index is equal to the length or n of the array which is

169
00:08:17,860 --> 00:08:18,610
given to us.

170
00:08:18,610 --> 00:08:23,350
And if it is equal then we will push it to the results array, which is what we have over here.

171
00:08:23,350 --> 00:08:25,930
If it's not equal, we will go ahead.

172
00:08:25,930 --> 00:08:28,090
If it's equal, we will push and then we will return.

173
00:08:28,090 --> 00:08:28,390
Right.

174
00:08:28,390 --> 00:08:29,680
So let me just write that over here.

175
00:08:29,680 --> 00:08:33,970
But if it's not equal to the length then we will go through these steps.

176
00:08:33,970 --> 00:08:39,730
So let's just take this example where we have the input array 187 and walk through it so that we can

177
00:08:39,730 --> 00:08:40,450
understand it.

178
00:08:40,450 --> 00:08:47,260
Now initially we will call this helper function and we will pass zero as the index and we will numb's

179
00:08:47,260 --> 00:08:48,730
is the array which is given to us.

180
00:08:48,730 --> 00:08:52,000
And then we will have an empty subset which is this one over here.

181
00:08:52,000 --> 00:08:52,390
All right.

182
00:08:52,390 --> 00:08:57,460
So we are over here now is I, I is equal to zero at this point which is passed to it.

183
00:08:57,460 --> 00:08:59,800
So I is not equal to length which is three.

184
00:08:59,800 --> 00:09:00,040
Right.

185
00:09:00,040 --> 00:09:01,210
The length over here is three.

186
00:09:01,210 --> 00:09:02,110
So what do we do.

187
00:09:02,110 --> 00:09:02,980
We come over here.

188
00:09:02,980 --> 00:09:06,700
Now we call the helper function again which is a recursive call.

189
00:09:06,700 --> 00:09:08,110
And we increment I.

190
00:09:08,110 --> 00:09:11,980
And again we pass numb's and we pass subset which is empty at this point.

191
00:09:11,980 --> 00:09:12,430
Right.

192
00:09:12,430 --> 00:09:14,980
And in that again we come over here.

193
00:09:14,980 --> 00:09:15,250
Right.

194
00:09:15,250 --> 00:09:17,680
So you can see that we are actually moving in this way.

195
00:09:17,680 --> 00:09:18,160
Right.

196
00:09:18,160 --> 00:09:20,650
So we have the initial call where I is equal to zero.

197
00:09:20,650 --> 00:09:24,280
Then over here we incremented I and we made this call.

198
00:09:24,280 --> 00:09:24,520
Right.

199
00:09:24,520 --> 00:09:29,020
So we made this call that will again call the helper function I is not equal to three.

200
00:09:29,020 --> 00:09:32,800
So we come again over here we increment I and we make this call right.

201
00:09:32,800 --> 00:09:34,120
So we go ahead.

202
00:09:34,120 --> 00:09:39,340
You can see that visually we go from here to here from here to here and from here to here when we have

203
00:09:39,340 --> 00:09:41,680
this call finally I is equal to three.

204
00:09:41,680 --> 00:09:45,940
Therefore we will push whatever is there in our subset to our results array.

205
00:09:45,940 --> 00:09:49,120
And that's how we get this element over here in our results array.

206
00:09:49,330 --> 00:09:50,140
All right.

207
00:09:50,440 --> 00:09:52,000
So this part over here is done.

208
00:09:52,000 --> 00:09:53,590
Now what do we do.

209
00:09:53,590 --> 00:09:54,190
It returns.

210
00:09:54,190 --> 00:10:01,420
So this this line is done for the call where we got I where I was equal to two and two plus one gave

211
00:10:01,420 --> 00:10:01,900
us three.

212
00:10:01,900 --> 00:10:03,850
So we came over here and we pushed this.

213
00:10:03,850 --> 00:10:05,170
So this line is done.

214
00:10:05,170 --> 00:10:11,650
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

215
00:10:11,650 --> 00:10:12,760
I is equal to two, right.

216
00:10:12,760 --> 00:10:13,810
So I is equal to two.

217
00:10:13,840 --> 00:10:17,710
So we are making this call by pushing seven to the subset.

218
00:10:17,710 --> 00:10:18,970
And then we are coming over here.

219
00:10:18,970 --> 00:10:24,940
So num set I num set two at this point is seven because I is equal to two at that seven at that point.

220
00:10:24,940 --> 00:10:26,170
Right I is equal to two.

221
00:10:26,200 --> 00:10:28,750
So let me just write the indices zero one and two.

222
00:10:28,780 --> 00:10:31,510
So we are pushing seven to the empty subset.

223
00:10:31,510 --> 00:10:33,610
So this is how our subset looks like.

224
00:10:33,610 --> 00:10:36,430
And then we are making this call helper I plus one.

225
00:10:36,430 --> 00:10:37,540
So two plus one.

226
00:10:37,720 --> 00:10:39,400
So two plus one is three right.

227
00:10:39,400 --> 00:10:40,450
Two plus one is three.

228
00:10:40,450 --> 00:10:42,640
And the subset at that point is.

229
00:10:43,040 --> 00:10:44,600
An array with only seven.

230
00:10:44,600 --> 00:10:49,010
So again we come over here, we see I is equal to three at that point because we are over here.

231
00:10:49,010 --> 00:10:50,240
We did two plus one right.

232
00:10:50,240 --> 00:10:51,290
So I is equal to three.

233
00:10:51,290 --> 00:10:53,900
So at that point we are going to push this.

234
00:10:53,900 --> 00:10:56,720
That is this array with only seven to our results array.

235
00:10:56,720 --> 00:10:58,310
So that is this over here.

236
00:10:58,310 --> 00:11:01,340
And that is how we are going to get seven in our results.

237
00:11:01,340 --> 00:11:02,090
All right.

238
00:11:02,540 --> 00:11:04,130
So this call is also done.

239
00:11:04,130 --> 00:11:07,820
And after this we are just going to pop seven from the subset.

240
00:11:07,820 --> 00:11:09,470
So we added seven over here.

241
00:11:09,470 --> 00:11:11,630
And over here we are going to pop seven.

242
00:11:11,630 --> 00:11:14,480
So seven is also removed from the subset.

243
00:11:14,480 --> 00:11:16,910
And again our subset looks like this.

244
00:11:17,060 --> 00:11:17,600
All right.

245
00:11:17,630 --> 00:11:19,040
Now what do we do.

246
00:11:19,040 --> 00:11:20,750
Again we move in this direction right.

247
00:11:20,750 --> 00:11:21,830
We come over here.

248
00:11:21,830 --> 00:11:23,090
We come over here.

249
00:11:23,090 --> 00:11:28,520
And at this point when when we make this call we pass I as two.

250
00:11:28,550 --> 00:11:28,730
Right.

251
00:11:28,730 --> 00:11:30,890
Because we are increment at this point I is one.

252
00:11:30,890 --> 00:11:31,850
We increment it.

253
00:11:31,850 --> 00:11:34,730
So again all of this what we did was part of this call right.

254
00:11:34,730 --> 00:11:35,360
This call.

255
00:11:35,360 --> 00:11:36,260
So that is done.

256
00:11:36,260 --> 00:11:37,220
So that was this.

257
00:11:37,220 --> 00:11:38,120
So that is done.

258
00:11:38,120 --> 00:11:42,800
So then we come over here we push num at I and I over here is equal to one.

259
00:11:42,800 --> 00:11:43,790
So we push eight.

260
00:11:43,790 --> 00:11:45,800
So this is how our subset looks like.

261
00:11:45,800 --> 00:11:47,330
And then we call the helper function.

262
00:11:47,330 --> 00:11:49,820
So again we come over here we see I is equal to two.

263
00:11:49,820 --> 00:11:51,260
Over here it's not equal to three.

264
00:11:51,260 --> 00:11:56,480
So we come over here we increment I and we again call the helper function which is this call.

265
00:11:56,480 --> 00:12:00,260
And in this call we get eight added to the results array.

266
00:12:00,260 --> 00:12:04,640
So after that we are done with this line of code.

267
00:12:04,640 --> 00:12:05,060
Right.

268
00:12:05,060 --> 00:12:08,120
Then we push numb's at two because I is over here.

269
00:12:08,120 --> 00:12:08,510
Two right.

270
00:12:08,510 --> 00:12:09,710
So that's seven.

271
00:12:09,710 --> 00:12:11,330
So we push seven to the subset.

272
00:12:11,330 --> 00:12:14,030
So the subset looks like this eight comma seven.

273
00:12:14,030 --> 00:12:15,410
Again we increment I.

274
00:12:15,440 --> 00:12:17,360
So that is this call over here right.

275
00:12:17,360 --> 00:12:19,160
And I is equal to three.

276
00:12:19,160 --> 00:12:22,370
Therefore we push eight comma seven to the our results array.

277
00:12:22,370 --> 00:12:24,980
So in this manner you can see we are we are.

278
00:12:25,010 --> 00:12:26,750
We initially had this added.

279
00:12:26,750 --> 00:12:28,490
Then we had this added over here.

280
00:12:28,490 --> 00:12:31,370
Then we have the array with eight added over here.

281
00:12:31,370 --> 00:12:34,070
Then we have the array eight comma seven added over here.

282
00:12:34,070 --> 00:12:35,780
So this is also done right.

283
00:12:35,780 --> 00:12:37,580
So all of all of this is done.

284
00:12:37,580 --> 00:12:38,840
This was part of this call.

285
00:12:38,840 --> 00:12:39,290
Right.

286
00:12:39,290 --> 00:12:40,610
Again it will return.

287
00:12:40,610 --> 00:12:41,810
It will pop out seven.

288
00:12:41,810 --> 00:12:42,410
It will return.

289
00:12:42,410 --> 00:12:43,250
It will pop out eight.

290
00:12:43,250 --> 00:12:46,400
And our subset again will look as an empty subset.

291
00:12:46,400 --> 00:12:51,020
So you can notice over here that whenever we are adding something we are calling the helper function

292
00:12:51,020 --> 00:12:51,710
recursively.

293
00:12:51,710 --> 00:12:54,530
And then we are popping out or removing whatever we added.

294
00:12:54,530 --> 00:12:57,650
So this is so that we can reuse the same subset array.

295
00:12:57,650 --> 00:12:59,360
Whenever we are adding to the results.

296
00:12:59,360 --> 00:13:04,100
We will make a copy using the dot slice operator, and we will make a copy and add it to the results

297
00:13:04,100 --> 00:13:04,850
array over here.

298
00:13:04,850 --> 00:13:10,580
But apart from that, whenever we are adding or removing something from the subset, we are using the

299
00:13:10,580 --> 00:13:11,510
same subset array.

300
00:13:11,510 --> 00:13:14,420
So that is why whatever was added over here is removed over here.

301
00:13:14,420 --> 00:13:16,220
So you can see seven was added.

302
00:13:16,220 --> 00:13:21,350
We remove it, eight was added, we remove it and we get back over here which is our empty subset.

303
00:13:21,860 --> 00:13:22,280
All right.

304
00:13:22,280 --> 00:13:23,270
Now let's proceed.

305
00:13:23,270 --> 00:13:25,670
So we are done with these four elements.

306
00:13:25,670 --> 00:13:31,070
Now again let me just remove this also so that it's easy for us to track what is happening.

307
00:13:32,960 --> 00:13:33,680
All right.

308
00:13:33,680 --> 00:13:36,620
Now, again, this was part of this call.

309
00:13:36,620 --> 00:13:39,530
All of this, what we have done so far was part of this call.

310
00:13:39,530 --> 00:13:39,710
Right?

311
00:13:39,710 --> 00:13:41,270
And then we just made recursive calls.

312
00:13:41,270 --> 00:13:45,770
We went in this direction, then we went over here, we went over here, we went over here, we went

313
00:13:45,770 --> 00:13:46,940
over here and and over here.

314
00:13:46,940 --> 00:13:49,010
But all of this was part of this call.

315
00:13:49,010 --> 00:13:49,520
Right?

316
00:13:49,520 --> 00:13:53,510
Again, that was a call over here where we call the helper function.

317
00:13:53,510 --> 00:13:56,240
We incremented I and the subset was empty.

318
00:13:56,270 --> 00:13:59,930
Now we are done with this because all of this is done and it has returned.

319
00:13:59,930 --> 00:14:03,170
So this much is done and this line of code has executed.

320
00:14:03,170 --> 00:14:07,340
Now we come over here right at this point I is equal to zero, right.

321
00:14:07,340 --> 00:14:11,300
So we are going to push numb's at I, which is one to the subset.

322
00:14:11,300 --> 00:14:15,590
And then we are going to make this call over here which is calling the helper function.

323
00:14:15,590 --> 00:14:16,670
We are incrementing I.

324
00:14:16,700 --> 00:14:18,680
So I is equal to one at this point.

325
00:14:18,680 --> 00:14:19,490
Over here I is zero.

326
00:14:19,490 --> 00:14:20,780
So I is one at this point.

327
00:14:20,780 --> 00:14:22,550
And the subset looks like this.

328
00:14:22,550 --> 00:14:25,490
So it's an array with only one right.

329
00:14:25,490 --> 00:14:27,170
So again let me just wipe this.

330
00:14:28,220 --> 00:14:30,110
So we are over here now.

331
00:14:30,110 --> 00:14:35,330
As part of this call, we are going to recursively call again this where we increment I.

332
00:14:35,360 --> 00:14:36,440
So I is equal to two.

333
00:14:36,470 --> 00:14:41,480
Again we are going to call the helper function recursively and increment I where I is equal to three.

334
00:14:41,510 --> 00:14:43,370
We are not adding anything to the subset right.

335
00:14:43,370 --> 00:14:47,060
And that is how we will add this element to the results array.

336
00:14:47,060 --> 00:14:50,750
And then after we are done with this we go in this direction.

337
00:14:50,750 --> 00:14:52,520
At this point I is equal to two.

338
00:14:52,550 --> 00:14:57,440
So we are going to add seven which is the element in the array at the index two.

339
00:14:57,470 --> 00:14:57,620
Right.

340
00:14:57,620 --> 00:15:00,800
So we are going to add seven to the subset and we will increment I.

341
00:15:00,830 --> 00:15:03,320
So I is equal to three and we call the helper function.

342
00:15:03,320 --> 00:15:06,170
So we pushed one comma seven to the results array.

343
00:15:06,170 --> 00:15:07,040
So this is done.

344
00:15:07,040 --> 00:15:07,700
This is done.

345
00:15:07,700 --> 00:15:09,680
After this we added seven right.

346
00:15:09,680 --> 00:15:11,630
So we are going to pop seven from the subset.

347
00:15:11,630 --> 00:15:13,520
So we remove seven and we are done.

348
00:15:13,520 --> 00:15:18,560
So this was part of the uh the call where we don't add anything from here.

349
00:15:18,560 --> 00:15:19,760
Now that is done.

350
00:15:19,760 --> 00:15:22,640
Now we are going to push numb's at I where I is equal to one.

351
00:15:22,640 --> 00:15:25,400
So at index one we have element eight.

352
00:15:25,400 --> 00:15:28,490
We are going to push eight to the subset in element I.

353
00:15:28,520 --> 00:15:31,580
So I is equal to two and call the helper function again.

354
00:15:31,580 --> 00:15:34,760
From there we are going to not add anything and increment I.

355
00:15:34,790 --> 00:15:35,780
So I is equal to three.

356
00:15:35,780 --> 00:15:38,390
So one comma eight is added to the results array.

357
00:15:38,390 --> 00:15:39,170
We come back.

358
00:15:39,170 --> 00:15:40,160
So this call is done.

359
00:15:40,160 --> 00:15:43,190
And then we come over here we add seven.

360
00:15:43,190 --> 00:15:44,810
So because I is equal to two right.

361
00:15:44,810 --> 00:15:46,580
So at index two we have seven.

362
00:15:46,580 --> 00:15:47,720
You can see we have seven.

363
00:15:47,720 --> 00:15:50,360
So we add seven to our subset we increment I.

364
00:15:50,390 --> 00:15:51,380
So I is equal to three.

365
00:15:51,380 --> 00:15:54,650
And then we push one comma eight comma seven to our results array.

366
00:15:54,650 --> 00:15:55,730
And this call is done.

367
00:15:55,730 --> 00:15:56,780
We pop out seven.

368
00:15:56,780 --> 00:15:58,610
We come back we pop out eight.

369
00:15:58,610 --> 00:16:00,320
We come back and we pop out one.

370
00:16:00,320 --> 00:16:02,210
And again our subset is empty.

371
00:16:02,210 --> 00:16:04,100
So this is how this function works.

372
00:16:04,100 --> 00:16:11,090
And you can see that recursively we were able to get the power set which is a set of eight elements

373
00:16:11,090 --> 00:16:12,500
which is two to the power three.

374
00:16:12,500 --> 00:16:15,890
Because the array which is given to us had three elements.