1
00:00:00,390 --> 00:00:01,170
Hey there.

2
00:00:01,170 --> 00:00:02,250
Welcome back.

3
00:00:02,250 --> 00:00:08,610
Let's now go ahead and discuss the approach that we can take to solve this question.

4
00:00:08,610 --> 00:00:16,440
And before we do that, first let's try to understand why the previous approach that we discussed for

5
00:00:16,440 --> 00:00:23,220
the Subset's problem needs some changes for it to work in this scenario.

6
00:00:23,220 --> 00:00:25,530
So for this, let's take an example.

7
00:00:25,530 --> 00:00:31,050
Let's say the array which is given to us is 1337.

8
00:00:31,050 --> 00:00:35,580
Now let's just walk through the algorithm and see what happens.

9
00:00:35,580 --> 00:00:38,790
So initially we are considering this element over here.

10
00:00:38,790 --> 00:00:41,460
So we have a branch that includes it.

11
00:00:41,460 --> 00:00:43,950
And we have a branch that excludes it.

12
00:00:43,950 --> 00:00:47,940
Then we move on to this element over here and over here.

13
00:00:47,940 --> 00:00:51,180
Let's just include it and excluded.

14
00:00:51,180 --> 00:00:53,940
So we get one comma three and we get one.

15
00:00:53,940 --> 00:01:00,990
And over here when we apply the same thing for this element we get three and we get an empty set.

16
00:01:01,650 --> 00:01:04,560
Let's proceed to this element over here.

17
00:01:04,560 --> 00:01:13,350
Now when we include and exclude three to this array we get one, three, three and one comma three.

18
00:01:13,530 --> 00:01:19,350
Now when we do the same thing to this array, notice that again we have the element three.

19
00:01:19,350 --> 00:01:23,970
So when we include three to this array it becomes one comma three.

20
00:01:23,970 --> 00:01:26,880
And when we exclude three we have one.

21
00:01:26,880 --> 00:01:29,340
Now notice that there is a repetition.

22
00:01:29,340 --> 00:01:31,680
So these two are repeating.

23
00:01:31,680 --> 00:01:36,840
Now whatever comes down this these two branches would be repetitions.

24
00:01:36,840 --> 00:01:42,180
And our final output would not be without duplicates.

25
00:01:42,180 --> 00:01:45,390
So this is the problem of the previous approach.

26
00:01:45,390 --> 00:01:52,380
Now previously this was not a problem because it was guaranteed in the problem statement that the input

27
00:01:52,380 --> 00:01:54,720
array consists of unique elements.

28
00:01:54,720 --> 00:01:57,300
But over here that's not the case.

29
00:01:57,300 --> 00:01:59,400
So how do we solve this.

30
00:01:59,400 --> 00:02:06,210
So the way to solve this is to consider these two branches in a special way.

31
00:02:06,210 --> 00:02:11,970
So this branch over here and again we were dealing with this element which is three.

32
00:02:11,970 --> 00:02:19,260
So this branch over here has to be the branch that has one or more trees.

33
00:02:19,260 --> 00:02:26,280
And this branch over here, which was the branch that excluded this three should have zero threes.

34
00:02:26,970 --> 00:02:30,960
It cannot include any threes even down the line over here.

35
00:02:30,960 --> 00:02:32,880
Also we cannot include a three.

36
00:02:32,880 --> 00:02:40,740
So if we take this approach where when we include an element it not only means that we include that

37
00:02:40,740 --> 00:02:47,430
particular element, but it means that in that section of the branch we can include one or more repetitions

38
00:02:47,430 --> 00:02:48,150
of that element.

39
00:02:48,150 --> 00:02:50,970
But in the exclude branch.

40
00:02:51,120 --> 00:02:57,480
And this is where we change the algorithm from the previous solution that we have discussed for the

41
00:02:57,480 --> 00:02:58,470
subsets problem.

42
00:02:58,470 --> 00:03:07,290
So in the exclude branch we not only exclude this three over here, but we also exclude any other threes.

43
00:03:07,290 --> 00:03:12,660
And for this we would have to get the array which is given to us in a sorted manner.

44
00:03:12,660 --> 00:03:17,700
So initially if the array was 1373 we can just sort it.

45
00:03:17,700 --> 00:03:20,640
So we would get 1337.

46
00:03:20,640 --> 00:03:25,320
And then in the exclude branch we were dealing with this element.

47
00:03:25,320 --> 00:03:29,130
But we not only exclude this, we also exclude this.

48
00:03:29,130 --> 00:03:35,880
And the next element that we consider in this branch has to be the next unique value, which is seven.

49
00:03:35,880 --> 00:03:37,920
So let's see how this pans out.

50
00:03:37,920 --> 00:03:39,570
Now we proceed.

51
00:03:39,570 --> 00:03:42,030
So we have discussed that over here.

52
00:03:42,030 --> 00:03:46,290
We were dealing with this element and then we were considering the next element.

53
00:03:46,290 --> 00:03:50,970
So at this point when we are considering the value three we include three.

54
00:03:50,970 --> 00:03:56,070
We get one comma three we exclude three or any occurrences of three.

55
00:03:56,070 --> 00:03:57,780
And we get again one.

56
00:03:57,780 --> 00:04:05,460
But in the next level over here we again consider this three and we included an excluded we get 133

57
00:04:05,460 --> 00:04:06,480
and one three.

58
00:04:06,570 --> 00:04:14,400
But over here, because we excluded all occurrences of three, the next thing that we consider is seven.

59
00:04:14,400 --> 00:04:20,460
And when we include in the include step this over here changes to one comma seven.

60
00:04:20,460 --> 00:04:23,520
And the exclude step is one itself.

61
00:04:23,520 --> 00:04:26,340
And then in this manner we proceed over here.

62
00:04:26,340 --> 00:04:35,220
The next two uh elements or subsets that we get by including and excluding would be one, 337 and 133.

63
00:04:36,000 --> 00:04:38,850
And over here we get one, three, seven.

64
00:04:38,850 --> 00:04:40,560
So again the next element is seven right.

65
00:04:40,560 --> 00:04:41,820
We get one, three, seven.

66
00:04:41,820 --> 00:04:44,610
And when we exclude we get one three.

67
00:04:44,850 --> 00:04:49,380
In a similar manner over here we were dealing with this three over here.

68
00:04:49,380 --> 00:04:55,650
So only this branch will have threes because we have included three and we have excluded three over

69
00:04:55,650 --> 00:04:56,010
here.

70
00:04:56,010 --> 00:04:59,430
So the next element over here would be three comma three.

71
00:04:59,580 --> 00:05:02,070
And when we exclude we get three.

72
00:05:02,070 --> 00:05:06,990
And over here because we are not including any threes.

73
00:05:06,990 --> 00:05:09,810
So the next element under consideration is a seven.

74
00:05:09,810 --> 00:05:16,470
So in the next level we get seven when we include and an empty set when we exclude.

75
00:05:16,470 --> 00:05:18,930
And over here again we have seven.

76
00:05:18,930 --> 00:05:22,140
So we get 337 and three three.

77
00:05:22,140 --> 00:05:28,530
Similarly over here we can get three comma seven and three.

78
00:05:28,710 --> 00:05:37,620
So notice over here in this manner we were able to get all the unique subsets and there is no repetition

79
00:05:37,620 --> 00:05:39,330
or there are no duplicates.

80
00:05:39,330 --> 00:05:47,190
Now just to solidify our learning, let's try to see how the recursion tree would look like for an input

81
00:05:47,190 --> 00:05:49,950
that says 13337.

82
00:05:49,950 --> 00:05:53,070
So we have three times the value three occurring.

83
00:05:53,070 --> 00:05:56,850
So let's just draw this out to solidify our learning.

84
00:05:56,850 --> 00:06:00,240
So initially we are considering this element over here.

85
00:06:00,240 --> 00:06:01,500
So we include it.

86
00:06:01,530 --> 00:06:02,220
We get one.

87
00:06:02,220 --> 00:06:03,030
We exclude it.

88
00:06:03,030 --> 00:06:04,350
We get an empty array.

89
00:06:04,440 --> 00:06:08,100
Then we move on to this value which is three.

90
00:06:08,100 --> 00:06:13,830
And the branch that includes it has one comma three as the array.

91
00:06:13,830 --> 00:06:17,100
And the branch that excludes it has one itself.

92
00:06:17,100 --> 00:06:26,130
But then the significant change is that the next level of this branch will not consider this three or

93
00:06:26,130 --> 00:06:26,730
this three.

94
00:06:26,730 --> 00:06:29,880
It will consider the next unique value which is seven.

95
00:06:29,880 --> 00:06:32,670
So when we include this, we get one comma seven.

96
00:06:32,670 --> 00:06:35,370
And when we exclude it we get one.

97
00:06:35,370 --> 00:06:39,030
Now let's also draw this branch over here.

98
00:06:39,030 --> 00:06:42,480
Let's continue drawing it to solidify our learning.

99
00:06:42,480 --> 00:06:46,500
So over here we just included this three.

100
00:06:46,500 --> 00:06:51,390
And the next element under consideration is this three over here okay.

101
00:06:51,390 --> 00:06:52,860
So this is the next element.

102
00:06:52,860 --> 00:06:54,120
And we include it.

103
00:06:54,150 --> 00:06:55,500
We get 133.

104
00:06:55,530 --> 00:06:56,580
We exclude it.

105
00:06:56,610 --> 00:06:58,230
We get one comma three.

106
00:06:58,230 --> 00:07:04,890
Now the important thing is that in this branch we have just included this value which is a three.

107
00:07:04,890 --> 00:07:12,150
So that means that all the other occurrences of three are as well to be excluded in this branch.

108
00:07:12,150 --> 00:07:17,610
So the next element in this branch which can be included is a seven.

109
00:07:18,060 --> 00:07:19,200
So this is important.

110
00:07:19,470 --> 00:07:23,400
The next subset that we get when we include is 137.

111
00:07:23,400 --> 00:07:24,870
So this is very important.

112
00:07:24,870 --> 00:07:34,380
So we are recursively doing this whenever something is excluded that value and any other value which

113
00:07:34,380 --> 00:07:39,000
is equal to it which is again upcoming is also excluded.

114
00:07:39,000 --> 00:07:41,790
So this is how we can solve this question.

115
00:07:42,380 --> 00:07:46,670
And over here again we get one, three, three three and one, three, three.

116
00:07:47,120 --> 00:07:50,960
And then we can go ahead and include seven and exclude seven.

117
00:07:50,960 --> 00:07:53,090
And we do the same thing over here as well.

118
00:07:53,090 --> 00:07:58,580
So again remember the difference over here is that there is no difference in the include step.

119
00:07:58,820 --> 00:08:01,310
The difference is in the exclude step.

120
00:08:01,310 --> 00:08:10,490
So when we exclude a value we are not only excluding that value but all occurrences.

121
00:08:11,910 --> 00:08:13,230
That our upcoming.

122
00:08:14,890 --> 00:08:16,180
Of that value.

123
00:08:16,180 --> 00:08:16,840
All right.

124
00:08:16,840 --> 00:08:23,350
And again remember first we have to sort the array which is given to us so that if the array which was

125
00:08:23,350 --> 00:08:28,510
given to us looked something like this, we change this.

126
00:08:28,510 --> 00:08:35,530
Or let's say we had a three over here and then we have a seven over here, and then we have three and

127
00:08:35,530 --> 00:08:35,890
three.

128
00:08:35,890 --> 00:08:37,750
So we need to change this.

129
00:08:37,750 --> 00:08:45,100
So we change it to one, three, three, seven so that all the equal values are next to each other.