1 00:00:00,740 --> 00:00:01,700 Welcome back. 2 00:00:01,700 --> 00:00:07,070 So this is the code that we have just now written which is to find the power set of an array. 3 00:00:07,100 --> 00:00:08,990 Now let's walk through the code. 4 00:00:08,990 --> 00:00:13,250 And for this let's take the help of the diagram that we have previously drawn. 5 00:00:13,250 --> 00:00:13,550 Right. 6 00:00:13,550 --> 00:00:17,120 So this will help us to keep track of the recursions that's happening. 7 00:00:17,120 --> 00:00:21,710 Now let's say we have passed in this array over here one eight and seven. 8 00:00:21,710 --> 00:00:24,050 Now let's walk through the code with this. 9 00:00:24,050 --> 00:00:25,550 Now we call the function. 10 00:00:25,550 --> 00:00:27,230 And we pass this array over here. 11 00:00:27,230 --> 00:00:29,030 So numb's is 187 over here. 12 00:00:29,030 --> 00:00:31,910 And then we initialize output to be an empty array. 13 00:00:31,910 --> 00:00:34,730 So let this be our empty array which is the output. 14 00:00:34,880 --> 00:00:38,390 Now we come over here we have our helper function defined. 15 00:00:38,390 --> 00:00:39,620 And then we come over here. 16 00:00:39,620 --> 00:00:41,270 And the helper function is called. 17 00:00:41,270 --> 00:00:46,100 We pass in the array 187 and the index zero is passed. 18 00:00:46,100 --> 00:00:49,490 And then our subset at this point is an empty array. 19 00:00:49,490 --> 00:00:50,840 So we come over here. 20 00:00:50,840 --> 00:00:53,360 Now at this point I is equal to zero. 21 00:00:53,360 --> 00:00:56,150 So I is not equal to numb's dot length which is three. 22 00:00:56,150 --> 00:00:56,330 Right. 23 00:00:56,330 --> 00:00:57,560 So the length over here is three. 24 00:00:57,560 --> 00:00:58,880 So we come over here. 25 00:00:59,480 --> 00:00:59,780 All right. 26 00:00:59,780 --> 00:01:02,210 So this is the part where we are in this diagram. 27 00:01:02,210 --> 00:01:05,690 And then we are going to call recursively the same helper function. 28 00:01:05,690 --> 00:01:07,850 And we are passing the array 187. 29 00:01:07,850 --> 00:01:10,250 And I at this point is equal to one. 30 00:01:10,250 --> 00:01:12,380 And the subset at this point is empty. 31 00:01:12,380 --> 00:01:14,540 So you can see that we came over here. 32 00:01:14,540 --> 00:01:14,840 All right. 33 00:01:14,840 --> 00:01:17,030 So at this point I is equal to one. 34 00:01:17,030 --> 00:01:22,010 Now again we come to the helper function and I is equal to one. 35 00:01:22,010 --> 00:01:25,730 At this point you can see we are over here and I is not equal to three. 36 00:01:25,730 --> 00:01:29,720 So again we come to this part where again we call the helper function. 37 00:01:29,720 --> 00:01:31,280 And I is incremented. 38 00:01:31,280 --> 00:01:32,210 So I is equal to two. 39 00:01:32,240 --> 00:01:33,950 So we can see that we come over here. 40 00:01:33,950 --> 00:01:34,400 Right. 41 00:01:34,400 --> 00:01:36,290 So I is equal to two at this point. 42 00:01:36,290 --> 00:01:40,820 And again the subset is is the subset array is empty. 43 00:01:41,000 --> 00:01:44,420 And we come and call the helper function again. 44 00:01:44,420 --> 00:01:45,470 So we are over here again. 45 00:01:45,470 --> 00:01:48,200 At this point I is equal to two. 46 00:01:48,230 --> 00:01:50,060 So it's not equal to numb's dot length. 47 00:01:50,060 --> 00:01:55,430 So we come over here and we call the helper function again with I is equal to three at this point which 48 00:01:55,430 --> 00:01:56,270 is this over here. 49 00:01:56,270 --> 00:01:58,250 So at this point I is equal to three. 50 00:01:58,250 --> 00:01:58,670 All right. 51 00:01:58,670 --> 00:01:59,780 So we are again over here. 52 00:01:59,780 --> 00:02:00,980 Let me just clear this. 53 00:02:00,980 --> 00:02:03,650 So that we can keep track of what's happening. 54 00:02:04,350 --> 00:02:06,480 So we are over here I is equal to three. 55 00:02:06,480 --> 00:02:10,770 And at this point we see that I is equal to numb's dot length which is three. 56 00:02:10,770 --> 00:02:15,960 So we are going to push a copy of what is there in the subset which is an empty array. 57 00:02:15,960 --> 00:02:16,200 Right. 58 00:02:16,200 --> 00:02:21,090 So subset dot slice means we are making a copy of this and we are pushing it to the output array. 59 00:02:21,090 --> 00:02:22,500 So let's write that over here. 60 00:02:22,500 --> 00:02:23,970 So we are getting this copy over here. 61 00:02:23,970 --> 00:02:26,610 And this is added to the output array. 62 00:02:26,610 --> 00:02:28,770 Now we are going to return right. 63 00:02:28,770 --> 00:02:31,200 So this call ends because we are returning over here. 64 00:02:31,200 --> 00:02:33,630 So the help of function call over here is ended. 65 00:02:33,630 --> 00:02:34,680 Now we come back. 66 00:02:34,680 --> 00:02:39,390 So we are done with this call where I was equal to two. 67 00:02:39,390 --> 00:02:39,630 Right. 68 00:02:39,630 --> 00:02:40,650 So I was equal to two. 69 00:02:40,680 --> 00:02:42,840 So two plus one gave us three. 70 00:02:42,840 --> 00:02:43,740 And that was this call. 71 00:02:43,740 --> 00:02:44,340 So that is over. 72 00:02:44,370 --> 00:02:46,590 This is over now we come back. 73 00:02:46,590 --> 00:02:49,050 Now what we are doing over here, we come to this line. 74 00:02:49,050 --> 00:02:53,100 And at this point we are pushing Numb's at I and I is equal to two. 75 00:02:53,100 --> 00:02:53,310 Right. 76 00:02:53,310 --> 00:02:55,770 So this is zero, this is one, this is two. 77 00:02:55,800 --> 00:02:57,900 So we are pushing seven to the subset. 78 00:02:57,900 --> 00:02:59,700 So that is what we are getting over here. 79 00:02:59,700 --> 00:03:01,440 And then we are calling the helper function. 80 00:03:01,440 --> 00:03:07,770 So this is a helper function called where the subset is this array over here which has seven as an element. 81 00:03:07,770 --> 00:03:11,130 And I at this point is two plus one which is three. 82 00:03:11,130 --> 00:03:11,310 Right. 83 00:03:11,310 --> 00:03:13,650 So we are coming again we are calling the helper function. 84 00:03:13,650 --> 00:03:14,730 We are coming again over here. 85 00:03:14,730 --> 00:03:17,520 And we see that I is equal to numb's dot length. 86 00:03:17,520 --> 00:03:22,530 So we are going to push a copy of the subset which is this over here to the output array. 87 00:03:22,530 --> 00:03:24,150 So we are getting seven over here. 88 00:03:24,950 --> 00:03:26,000 And then we are returning. 89 00:03:26,000 --> 00:03:27,560 So this call ends over here. 90 00:03:27,560 --> 00:03:33,560 So we are done with this and we're done with pushing seven to the subset we call the helper function 91 00:03:33,560 --> 00:03:36,320 with uh the subset having the element seven. 92 00:03:36,320 --> 00:03:37,310 So that is also done. 93 00:03:37,310 --> 00:03:38,630 Now we come out. 94 00:03:38,630 --> 00:03:40,160 So because this returns over here right. 95 00:03:40,160 --> 00:03:41,360 So we come back over here. 96 00:03:41,360 --> 00:03:43,850 Now at this point we are going to pop seven. 97 00:03:43,850 --> 00:03:45,860 So we added seven to the subset. 98 00:03:45,860 --> 00:03:48,080 Now we're going to remove seven from the subset. 99 00:03:48,080 --> 00:03:51,800 So again our subset at this point becomes an empty array. 100 00:03:51,800 --> 00:03:55,670 So we are doing this because we are going to use the same subset array. 101 00:03:55,670 --> 00:03:57,560 So we don't want to make copies right. 102 00:03:57,560 --> 00:03:59,990 So when we push to the output array we make a copy. 103 00:03:59,990 --> 00:04:03,020 But again throughout this we are going to use the same subset array. 104 00:04:03,230 --> 00:04:04,850 So we are popping seven. 105 00:04:04,850 --> 00:04:07,430 And this is how our subset looks at this point. 106 00:04:07,430 --> 00:04:08,960 And we are done right. 107 00:04:08,960 --> 00:04:10,850 So this part over here is done. 108 00:04:10,850 --> 00:04:16,580 Now this was part of the call where again let me just clear this up so that we can keep track of it. 109 00:04:16,580 --> 00:04:19,550 So we came to this part as part of this call. 110 00:04:19,550 --> 00:04:19,760 Right. 111 00:04:19,760 --> 00:04:24,110 So it came from I is I was equal to one, I was equal to one. 112 00:04:24,110 --> 00:04:25,970 And one plus one gave us two. 113 00:04:26,000 --> 00:04:27,710 So that is how we came over here. 114 00:04:27,710 --> 00:04:27,890 Right. 115 00:04:27,890 --> 00:04:29,540 So that is how we came over here. 116 00:04:29,540 --> 00:04:34,250 And once we came over here we recursively call the helper function and came here and then here. 117 00:04:34,250 --> 00:04:35,210 So this is done. 118 00:04:35,210 --> 00:04:37,100 Now we come again over here. 119 00:04:37,100 --> 00:04:42,020 So this part over here of this call right again we can we have to visually track this because this is 120 00:04:42,020 --> 00:04:43,190 a recursive solution. 121 00:04:43,190 --> 00:04:46,700 So to make it intuitive that's why I have this diagram over here. 122 00:04:46,700 --> 00:04:49,400 So this part over here this call is done. 123 00:04:49,400 --> 00:04:50,660 So this line over here is done. 124 00:04:50,660 --> 00:04:53,660 Right now we are going to push Numb's at I. 125 00:04:53,660 --> 00:04:55,400 And I at this point is equal to one. 126 00:04:55,400 --> 00:04:57,560 So eight eight is pushed to the subset. 127 00:04:57,560 --> 00:05:00,080 So our subset looks like this at this point. 128 00:05:00,080 --> 00:05:02,780 And then we are going to have a helper function called right. 129 00:05:03,200 --> 00:05:04,970 So again this is done this is done. 130 00:05:04,970 --> 00:05:06,590 This this line over here was done. 131 00:05:06,590 --> 00:05:12,770 So now we are having this call over here where the subset is an array with eight. 132 00:05:12,770 --> 00:05:14,810 And I at this point is one. 133 00:05:14,810 --> 00:05:17,420 So we are passing one plus one which is equal to two. 134 00:05:17,450 --> 00:05:17,900 Right. 135 00:05:17,900 --> 00:05:24,200 So we are coming again to the helper function because this is called now once we are over here we check 136 00:05:24,200 --> 00:05:25,520 whether I is equal to three. 137 00:05:25,520 --> 00:05:27,200 No I is equal to two at this point. 138 00:05:27,200 --> 00:05:27,530 Right. 139 00:05:27,530 --> 00:05:29,090 So we passed one plus one. 140 00:05:29,090 --> 00:05:30,080 So I is equal to two. 141 00:05:30,110 --> 00:05:31,430 So we come over here. 142 00:05:31,430 --> 00:05:34,220 Now we are going to again call the helper function. 143 00:05:34,220 --> 00:05:35,450 And we are passing this. 144 00:05:35,450 --> 00:05:36,860 This is the subset at this point. 145 00:05:36,860 --> 00:05:38,540 And I is going to be incremented. 146 00:05:38,540 --> 00:05:39,860 So that is this call over here. 147 00:05:39,860 --> 00:05:41,930 So we come over here I is equal to three. 148 00:05:41,930 --> 00:05:44,180 Again we come over here we see I is equal to three. 149 00:05:44,180 --> 00:05:47,450 So we push to the output array what we have over here. 150 00:05:47,450 --> 00:05:51,470 So we get comma eight the array with only element eight over here. 151 00:05:51,470 --> 00:05:53,930 So this call is also done because it returns over here. 152 00:05:53,930 --> 00:05:55,070 So this is also done. 153 00:05:55,070 --> 00:05:58,880 Now we are done with this call where I was equal to two. 154 00:05:58,880 --> 00:05:59,060 Right. 155 00:05:59,060 --> 00:06:00,890 So this is the call where I is equal to two. 156 00:06:00,890 --> 00:06:01,940 And we did this call. 157 00:06:01,940 --> 00:06:04,040 So this one over here that is completed. 158 00:06:04,490 --> 00:06:05,660 So we come over here. 159 00:06:05,660 --> 00:06:09,860 Now we are going to push to this numb's at I and I is equal to two. 160 00:06:09,890 --> 00:06:11,300 So nums at I is seven. 161 00:06:11,300 --> 00:06:13,880 So we are going to push seven to this array over here. 162 00:06:13,880 --> 00:06:15,500 And we get eight comma seven. 163 00:06:15,500 --> 00:06:18,710 And with this we are calling the helper function and incrementing I. 164 00:06:18,740 --> 00:06:19,940 So I over here is three. 165 00:06:19,940 --> 00:06:21,950 And this is how our subset looks like. 166 00:06:21,950 --> 00:06:25,280 Again we come over here I is equal to numb's dot length at that point. 167 00:06:25,280 --> 00:06:30,170 So we push eight comma seven the array eight comma seven to our output array and we return. 168 00:06:30,170 --> 00:06:35,450 So this is also done now at this point this this this is this is completed right. 169 00:06:35,450 --> 00:06:37,040 Its left and its right. 170 00:06:37,040 --> 00:06:40,010 Or adding and not adding and adding is completed. 171 00:06:40,010 --> 00:06:42,680 So we come over here and we pop. 172 00:06:42,680 --> 00:06:42,920 Right. 173 00:06:42,920 --> 00:06:46,730 So at this point uh, when we come out of this we just added seven. 174 00:06:46,730 --> 00:06:47,750 So we pop seven. 175 00:06:47,750 --> 00:06:49,280 So we remove seven from this. 176 00:06:49,280 --> 00:06:51,800 Now when we come out of it we added eight. 177 00:06:51,800 --> 00:06:54,170 So at this point we had added eight right. 178 00:06:54,170 --> 00:06:57,110 So again over here we are going to remove eight also. 179 00:06:57,110 --> 00:06:58,880 And we get back to this place. 180 00:06:58,880 --> 00:07:01,250 So this is again how our subset looks like. 181 00:07:01,250 --> 00:07:07,010 Let me just clear this so that we can keep track and we can continue tracing the algorithm. 182 00:07:08,450 --> 00:07:08,870 All right. 183 00:07:08,870 --> 00:07:11,330 So now we have completed this call. 184 00:07:11,330 --> 00:07:13,010 Now what do we do after this? 185 00:07:13,010 --> 00:07:14,270 Now over here. 186 00:07:14,450 --> 00:07:16,310 It was part of this call, right? 187 00:07:16,310 --> 00:07:18,710 All of this what we did was part of this call. 188 00:07:18,710 --> 00:07:19,190 Right? 189 00:07:19,190 --> 00:07:24,500 Which was when we passed the empty subset and I was equal to zero. 190 00:07:24,500 --> 00:07:25,790 So we passed zero plus one. 191 00:07:25,790 --> 00:07:27,170 So it was part of this call. 192 00:07:27,170 --> 00:07:30,290 Whatever we did so far so and that part is completed. 193 00:07:30,290 --> 00:07:31,790 So we come back to this. 194 00:07:31,790 --> 00:07:35,450 Now we are going to push numb's at I and I is equal to zero. 195 00:07:35,450 --> 00:07:36,920 So we are going to push one. 196 00:07:36,920 --> 00:07:38,450 So we are going in this direction. 197 00:07:38,450 --> 00:07:40,820 We are going to push and then we are going to make the helper call. 198 00:07:40,820 --> 00:07:42,020 So this is this helper call. 199 00:07:42,020 --> 00:07:42,470 All right. 200 00:07:42,470 --> 00:07:47,510 So where the subset is uh an array with only one and I is incremented. 201 00:07:47,510 --> 00:07:50,420 So I at this point becomes equal to one. 202 00:07:50,420 --> 00:07:52,070 So zero plus one it's one. 203 00:07:52,070 --> 00:07:54,110 So we we have this call. 204 00:07:54,110 --> 00:07:55,220 So this part is completed. 205 00:07:55,220 --> 00:07:56,390 So we have this call. 206 00:07:56,390 --> 00:07:59,780 And as part of this call again we come to the helper function. 207 00:07:59,780 --> 00:08:01,070 We move to the left right. 208 00:08:01,070 --> 00:08:04,340 So we increment I and we don't add anything to it. 209 00:08:04,340 --> 00:08:05,630 So that is this call. 210 00:08:05,630 --> 00:08:08,900 And again as part of this call we come back to the helper function. 211 00:08:08,900 --> 00:08:14,060 We again call it without with incrementing I and without adding anything which is this call at which 212 00:08:14,060 --> 00:08:17,510 point later we have I is equal to three. 213 00:08:17,510 --> 00:08:20,480 We push this over here and this call is done right. 214 00:08:20,480 --> 00:08:25,790 Similarly, after that is done again we push numb's at I, which will be seven at that point because 215 00:08:25,790 --> 00:08:27,290 I is equal to two when we are over here. 216 00:08:27,290 --> 00:08:27,530 Right. 217 00:08:27,530 --> 00:08:32,840 So we push two and then we make this call which adds one comma seven to our output array. 218 00:08:32,840 --> 00:08:34,850 So this is also done when it returns. 219 00:08:34,850 --> 00:08:37,550 And after it returns we are going to pop seven. 220 00:08:37,550 --> 00:08:38,810 So we are going to remove seven. 221 00:08:38,810 --> 00:08:42,920 And when we come back over here we have removed seven. 222 00:08:42,920 --> 00:08:44,600 So this is how it looks like right. 223 00:08:44,600 --> 00:08:47,300 So the left part this is done right. 224 00:08:47,300 --> 00:08:51,110 This is done when I was equal to uh one right. 225 00:08:51,110 --> 00:08:53,540 So one plus one gave us two and we had this call. 226 00:08:53,540 --> 00:08:56,690 So now we are going to have the call where we add. 227 00:08:56,690 --> 00:08:58,490 So at this point I is equal to one. 228 00:08:58,490 --> 00:08:59,510 We are going to add eight. 229 00:08:59,510 --> 00:09:01,520 We get one comma eight and I is equal to two. 230 00:09:01,520 --> 00:09:02,300 At this point. 231 00:09:02,300 --> 00:09:03,320 Again we go left. 232 00:09:03,320 --> 00:09:05,060 So we add one comma eight. 233 00:09:05,450 --> 00:09:06,980 And this call is done. 234 00:09:06,980 --> 00:09:09,680 And we come back and we add seven. 235 00:09:09,680 --> 00:09:12,620 So that also is added to the output array. 236 00:09:12,620 --> 00:09:14,690 At this point we remove seven. 237 00:09:14,690 --> 00:09:16,670 We come back over here we remove eight. 238 00:09:16,670 --> 00:09:17,870 We come back over here. 239 00:09:17,870 --> 00:09:21,890 And finally we remove one which is this over here when we had added. 240 00:09:21,890 --> 00:09:24,890 So when this was adding one when we come back to that call. 241 00:09:24,890 --> 00:09:25,070 Right. 242 00:09:25,070 --> 00:09:29,180 So once that this call is completed we come back and we remove one also. 243 00:09:29,180 --> 00:09:30,890 So we get our output over here. 244 00:09:30,890 --> 00:09:32,960 And this is how this function works. 245 00:09:32,960 --> 00:09:35,600 Now let's just summarize what is happening over here. 246 00:09:36,990 --> 00:09:44,760 So we can see that if we trace the algorithm on a high level, what it is doing is first it comes over 247 00:09:44,760 --> 00:09:47,520 here, then we recursively call it again. 248 00:09:47,520 --> 00:09:48,300 We come over here. 249 00:09:48,300 --> 00:09:49,800 At this point this is added. 250 00:09:49,800 --> 00:09:51,840 Then we add seven. 251 00:09:51,840 --> 00:09:54,030 Then we come back. 252 00:09:54,030 --> 00:09:55,320 We add eight. 253 00:09:55,320 --> 00:09:57,840 Then we print eight over here. 254 00:09:57,840 --> 00:09:58,950 Then we add seven. 255 00:09:58,950 --> 00:10:00,930 So you can see that this is how the algorithm works. 256 00:10:00,930 --> 00:10:02,400 Then we go all the way up. 257 00:10:02,400 --> 00:10:04,860 We go this way, we go this way and we go this way. 258 00:10:04,860 --> 00:10:06,060 We have added it over here. 259 00:10:06,060 --> 00:10:07,830 Then we add this one over here. 260 00:10:07,830 --> 00:10:13,290 We come back, then we come over here and we come over here at that point, which we add the array one 261 00:10:13,290 --> 00:10:13,860 comma eight. 262 00:10:13,860 --> 00:10:17,940 And then we come over here and at this point we add one comma eight comma seven. 263 00:10:17,940 --> 00:10:20,370 And that is how we are getting the output. 264 00:10:20,400 --> 00:10:23,790 Now let's take a look at the space and time complexity. 265 00:10:23,790 --> 00:10:27,210 We have already discussed that but let's just quickly take a relook at it. 266 00:10:27,210 --> 00:10:31,350 Over here we can see that the input array had three elements at this point. 267 00:10:31,350 --> 00:10:35,970 And the power set will have two to the power n elements right which is eight. 268 00:10:35,970 --> 00:10:38,550 So we have we can see that there are eight elements over here. 269 00:10:38,550 --> 00:10:40,560 So that is two to the power n. 270 00:10:41,070 --> 00:10:46,980 Now for each of these for the the number of times we are pushing elements into these subsets can range 271 00:10:46,980 --> 00:10:47,820 from zero. 272 00:10:47,820 --> 00:10:52,230 At this point it's 0112, one, two, two and three. 273 00:10:52,230 --> 00:10:55,140 So it's ranging from zero to 3 or 0 to n. 274 00:10:55,140 --> 00:10:58,950 So on an average we are doing n by two times pushing to a subset. 275 00:10:58,950 --> 00:11:04,740 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. 276 00:11:04,740 --> 00:11:06,060 And again this is a constant. 277 00:11:06,060 --> 00:11:07,410 So we can just avoid it. 278 00:11:07,410 --> 00:11:12,870 That's why the time complexity of this algorithm is of the order of two to the power n into n, and 279 00:11:12,870 --> 00:11:17,940 the space complexity is also of the order of two to the power n into n, because we can see that in 280 00:11:17,940 --> 00:11:20,970 these subsets, right there are two to the power n subsets. 281 00:11:20,970 --> 00:11:26,490 And on average we can say there are n by two elements per subset because it is ranging from zero to 282 00:11:26,490 --> 00:11:26,760 n. 283 00:11:26,760 --> 00:11:29,220 So again it's two to the power n into n by two. 284 00:11:29,220 --> 00:11:31,920 And I'm just removing one by two because it's a constant. 285 00:11:31,920 --> 00:11:37,230 So that's why the space complexity also of this solution is O of two to the power n into n.