Hey there.
Welcome back.
Let's now go ahead and discuss the approach that we can take to solve this question.
And before we do that, first let's try to understand why the previous approach that we discussed for
the Subset's problem needs some changes for it to work in this scenario.
So for this, let's take an example.
Let's say the array which is given to us is 1337.
Now let's just walk through the algorithm and see what happens.
So initially we are considering this element over here.
So we have a branch that includes it.
And we have a branch that excludes it.
Then we move on to this element over here and over here.
Let's just include it and excluded.
So we get one comma three and we get one.
And over here when we apply the same thing for this element we get three and we get an empty set.
Let's proceed to this element over here.
Now when we include and exclude three to this array we get one, three, three and one comma three.
Now when we do the same thing to this array, notice that again we have the element three.
So when we include three to this array it becomes one comma three.
And when we exclude three we have one.
Now notice that there is a repetition.
So these two are repeating.
Now whatever comes down this these two branches would be repetitions.
And our final output would not be without duplicates.
So this is the problem of the previous approach.
Now previously this was not a problem because it was guaranteed in the problem statement that the input
array consists of unique elements.
But over here that's not the case.
So how do we solve this.
So the way to solve this is to consider these two branches in a special way.
So this branch over here and again we were dealing with this element which is three.
So this branch over here has to be the branch that has one or more trees.
And this branch over here, which was the branch that excluded this three should have zero threes.
It cannot include any threes even down the line over here.
Also we cannot include a three.
So if we take this approach where when we include an element it not only means that we include that
particular element, but it means that in that section of the branch we can include one or more repetitions
of that element.
But in the exclude branch.
And this is where we change the algorithm from the previous solution that we have discussed for the
subsets problem.
So in the exclude branch we not only exclude this three over here, but we also exclude any other threes.
And for this we would have to get the array which is given to us in a sorted manner.
So initially if the array was 1373 we can just sort it.
So we would get 1337.
And then in the exclude branch we were dealing with this element.
But we not only exclude this, we also exclude this.
And the next element that we consider in this branch has to be the next unique value, which is seven.
So let's see how this pans out.
Now we proceed.
So we have discussed that over here.
We were dealing with this element and then we were considering the next element.
So at this point when we are considering the value three we include three.
We get one comma three we exclude three or any occurrences of three.
And we get again one.
But in the next level over here we again consider this three and we included an excluded we get 133
and one three.
But over here, because we excluded all occurrences of three, the next thing that we consider is seven.
And when we include in the include step this over here changes to one comma seven.
And the exclude step is one itself.
And then in this manner we proceed over here.
The next two uh elements or subsets that we get by including and excluding would be one, 337 and 133.
And over here we get one, three, seven.
So again the next element is seven right.
We get one, three, seven.
And when we exclude we get one three.
In a similar manner over here we were dealing with this three over here.
So only this branch will have threes because we have included three and we have excluded three over
here.
So the next element over here would be three comma three.
And when we exclude we get three.
And over here because we are not including any threes.
So the next element under consideration is a seven.
So in the next level we get seven when we include and an empty set when we exclude.
And over here again we have seven.
So we get 337 and three three.
Similarly over here we can get three comma seven and three.
So notice over here in this manner we were able to get all the unique subsets and there is no repetition
or there are no duplicates.
Now just to solidify our learning, let's try to see how the recursion tree would look like for an input
that says 13337.
So we have three times the value three occurring.
So let's just draw this out to solidify our learning.
So initially we are considering this element over here.
So we include it.
We get one.
We exclude it.
We get an empty array.
Then we move on to this value which is three.
And the branch that includes it has one comma three as the array.
And the branch that excludes it has one itself.
But then the significant change is that the next level of this branch will not consider this three or
this three.
It will consider the next unique value which is seven.
So when we include this, we get one comma seven.
And when we exclude it we get one.
Now let's also draw this branch over here.
Let's continue drawing it to solidify our learning.
So over here we just included this three.
And the next element under consideration is this three over here okay.
So this is the next element.
And we include it.
We get 133.
We exclude it.
We get one comma three.
Now the important thing is that in this branch we have just included this value which is a three.
So that means that all the other occurrences of three are as well to be excluded in this branch.
So the next element in this branch which can be included is a seven.
So this is important.
The next subset that we get when we include is 137.
So this is very important.
So we are recursively doing this whenever something is excluded that value and any other value which
is equal to it which is again upcoming is also excluded.
So this is how we can solve this question.
And over here again we get one, three, three three and one, three, three.
And then we can go ahead and include seven and exclude seven.
And we do the same thing over here as well.
So again remember the difference over here is that there is no difference in the include step.
The difference is in the exclude step.
So when we exclude a value we are not only excluding that value but all occurrences.
That our upcoming.
Of that value.
All right.
And again remember first we have to sort the array which is given to us so that if the array which was
given to us looked something like this, we change this.
Or let's say we had a three over here and then we have a seven over here, and then we have three and
three.
So we need to change this.
So we change it to one, three, three, seven so that all the equal values are next to each other.