1
00:00:00,730 --> 00:00:01,780
Welcome back.

2
00:00:01,780 --> 00:00:05,680
Let's now code the solution which we discussed in the previous video.

3
00:00:05,680 --> 00:00:09,790
Now for this we are going to write a function and let's just call it power set.

4
00:00:11,950 --> 00:00:16,390
And this function is going to take in the array which is given to us.

5
00:00:16,420 --> 00:00:18,190
So let's call the array numb's.

6
00:00:19,740 --> 00:00:23,970
All right, now over here inside this we are going to have the output array.

7
00:00:23,970 --> 00:00:26,010
So let's just call it output itself.

8
00:00:26,530 --> 00:00:32,140
And you're going to have a helper function, which we will recursively call, and at the end we will

9
00:00:32,140 --> 00:00:33,580
just return this output.

10
00:00:34,610 --> 00:00:36,020
So this is what we're going to do.

11
00:00:36,020 --> 00:00:36,410
Now.

12
00:00:36,410 --> 00:00:38,660
Let's go ahead and write the helper function.

13
00:00:39,170 --> 00:00:41,090
Now let's call it helper itself.

14
00:00:41,090 --> 00:00:45,050
So const helper is equal to function.

15
00:00:45,050 --> 00:00:47,870
And this function is going to take in the array.

16
00:00:47,870 --> 00:00:51,530
And it is going to take in the index I and a subset.

17
00:00:51,530 --> 00:00:51,770
Right.

18
00:00:51,770 --> 00:00:53,510
So the subset which we are working with.

19
00:00:53,510 --> 00:01:00,200
And then inside this helper function we are going to check whether I is equal to the length of the given

20
00:01:00,200 --> 00:01:00,620
array.

21
00:01:00,620 --> 00:01:04,370
So if I is equal to numb's dot length.

22
00:01:05,110 --> 00:01:08,890
If that is the case, then we will push the subset.

23
00:01:08,890 --> 00:01:10,180
That is what we are working with.

24
00:01:10,180 --> 00:01:13,570
We will make a copy of the subset and we will push it to the output array.

25
00:01:13,570 --> 00:01:13,810
Right.

26
00:01:13,810 --> 00:01:16,060
So we will say output dot push.

27
00:01:17,790 --> 00:01:19,800
And then we'll say subset.

28
00:01:20,910 --> 00:01:22,230
Dot slice.

29
00:01:23,200 --> 00:01:23,590
Right.

30
00:01:23,590 --> 00:01:29,170
So this is where we are using dot slice over here so that we are making a copy of the subset array at

31
00:01:29,170 --> 00:01:29,800
that point.

32
00:01:29,800 --> 00:01:31,660
And we are pushing it to the output array.

33
00:01:31,690 --> 00:01:32,230
All right.

34
00:01:32,230 --> 00:01:34,570
And after we are done with this we can just return.

35
00:01:34,570 --> 00:01:35,380
So return.

36
00:01:35,770 --> 00:01:36,040
All right.

37
00:01:36,070 --> 00:01:39,670
Now if this is not the case then we will have two cases right.

38
00:01:39,670 --> 00:01:43,630
We will have one case where we don't add the element at the ith index.

39
00:01:43,630 --> 00:01:46,000
And we will have a case where we add the element right.

40
00:01:46,000 --> 00:01:48,100
So we will have don't add and add.

41
00:01:48,100 --> 00:01:49,120
Two cases are there.

42
00:01:49,150 --> 00:01:52,960
Now first let's call the helper function where we don't add the i'th element.

43
00:01:52,960 --> 00:01:54,340
So we say helper.

44
00:01:54,340 --> 00:01:55,660
That's a recursive call.

45
00:01:55,660 --> 00:01:58,090
And again we pass the array numb's.

46
00:01:58,090 --> 00:02:00,190
And at this point we increment I.

47
00:02:00,220 --> 00:02:01,690
So we say I plus one.

48
00:02:02,680 --> 00:02:04,990
And over here we have subset.

49
00:02:05,750 --> 00:02:09,470
Which is what was the subset at when when we are over here.

50
00:02:09,470 --> 00:02:09,710
Right.

51
00:02:09,710 --> 00:02:13,310
So we don't change the subset we pass the same subset.

52
00:02:13,310 --> 00:02:17,180
That is we don't add anything to the subset and we just increment I.

53
00:02:17,210 --> 00:02:22,130
Now the other case is where we push to the subset the element at the ith index.

54
00:02:22,130 --> 00:02:24,200
So we can say subset dot push.

55
00:02:25,090 --> 00:02:26,290
Numb's at I.

56
00:02:28,040 --> 00:02:31,670
So we push the element at the ith index to the subset.

57
00:02:31,670 --> 00:02:33,320
And then we call the helper function.

58
00:02:33,320 --> 00:02:35,780
So helper numb's we pass numb's.

59
00:02:35,780 --> 00:02:38,180
And in this case also we increment I.

60
00:02:38,210 --> 00:02:39,380
So I plus one.

61
00:02:39,800 --> 00:02:43,730
And we pass the subset now so that we can use the same subset.

62
00:02:43,730 --> 00:02:48,350
After we have done with this we will just pop from subset what we just pushed to it.

63
00:02:48,350 --> 00:02:50,030
So we say subset dot pop.

64
00:02:51,950 --> 00:02:53,600
And we are done with the help of function.

65
00:02:53,600 --> 00:02:57,470
Now all we need to do is we need to call the helper function the first time.

66
00:02:57,470 --> 00:02:58,940
So we will do that over here.

67
00:02:58,940 --> 00:03:00,140
So we say helper.

68
00:03:00,140 --> 00:03:02,720
And at this point we are passing the array.

69
00:03:02,720 --> 00:03:06,020
And I at this point the index is going to be zero.

70
00:03:06,020 --> 00:03:08,300
And the subset is going to be an empty array.

71
00:03:08,300 --> 00:03:09,290
And that's it.

72
00:03:09,290 --> 00:03:12,110
Now let's call the function and let's see whether it's working.

73
00:03:12,110 --> 00:03:14,030
So the function is power set.

74
00:03:14,630 --> 00:03:16,970
And let's call it for an array.

75
00:03:16,970 --> 00:03:18,650
Let's say one two and three.

76
00:03:20,320 --> 00:03:20,620
All right.

77
00:03:20,620 --> 00:03:21,820
So let's just call it.

78
00:03:22,060 --> 00:03:23,860
Now let's look at the output.

79
00:03:23,860 --> 00:03:26,560
We can see that we have eight elements which is correct.

80
00:03:26,560 --> 00:03:30,250
We have seen that the power set should have two to the power n elements.

81
00:03:30,250 --> 00:03:31,600
And n in this case is three.

82
00:03:31,600 --> 00:03:35,080
So there should be two to the power 3 or 8 elements which is correct.

83
00:03:35,080 --> 00:03:36,430
Now let's look at the elements.

84
00:03:36,430 --> 00:03:38,770
We have the empty set empty array.

85
00:03:38,800 --> 00:03:42,970
Then we have three arrays with one element only so one, two and three.

86
00:03:42,970 --> 00:03:45,910
Then we have one and three, one and two which is correct.

87
00:03:45,910 --> 00:03:49,720
We have two and three and we have one, two and three.

88
00:03:49,720 --> 00:03:50,890
So yes that's correct.

89
00:03:50,890 --> 00:03:52,540
So we have a total of eight elements.

90
00:03:52,540 --> 00:03:53,680
So our function is working.

91
00:03:53,680 --> 00:03:55,840
Now what if we pass in an empty array.

92
00:03:56,410 --> 00:03:59,050
So we should have just one element right.

93
00:03:59,050 --> 00:04:02,770
So there's the the output array should have just one element.

94
00:04:02,770 --> 00:04:05,800
And that should be an array with zero elements.

95
00:04:05,800 --> 00:04:06,910
So yes that's correct.

96
00:04:06,910 --> 00:04:08,890
Now what if we have one element over here.

97
00:04:08,890 --> 00:04:10,180
Let's try that case.

98
00:04:11,110 --> 00:04:11,440
All right.

99
00:04:11,440 --> 00:04:14,620
In this case we have two to the power one which is two elements over here.

100
00:04:14,620 --> 00:04:15,460
That's correct.

101
00:04:15,460 --> 00:04:16,750
So this is empty.

102
00:04:16,750 --> 00:04:18,970
And this has just one element which is nine.

103
00:04:18,970 --> 00:04:20,830
So yes our function is working.

104
00:04:20,830 --> 00:04:24,850
Now let's take a sample input and walk through the code once more.

105
00:04:24,850 --> 00:04:29,620
And also take a relook at the space and time complexity of the solution.