Let's first discuss why the previous approach, the approach that we have discussed for solving the
permutations question will not work over here, or why we need to make a few changes to that approach.
So let's say the array which is given to us is one, one, two.
And as in the previous approach we would have two pointers.
So let's say initially I is equal to zero.
So when I is equal to zero j will take the values from 0 to 2.
So initially I is equal to zero and j is equal to zero.
Now if we swap the elements at zero and zero we will again get 112.
Then j is going to take the value one.
So we're going to swap the elements at zero and one indexes zero and one.
So at this point the array becomes again 112 because we just swapped these two elements again.
Right.
And this is also a one.
So again we are getting 112.
And then J is going to take the value two which is the next branch.
And over here we're going to swap the elements at index zero and two which are these two elements.
And when we do the swap the array looks like this which is 211.
Now notice over here the problem with this approach is that whatever we get from this branch and this
branch is going to be the same, right?
It's going to be duplicates because these two are one and the same.
So it's repeating over here.
And this is why the previous approach will not work as it is for this question.
And we need to make slight changes to avoid this branch over here.
So let's take a look at how we can do that.
So we need to avoid this branch because whatever comes over here is going to be a duplicate of what
is over here.
So to avoid this the approach that we can take is for this level over here where we have the value of
I as zero, we will create a hash table or a dictionary.
And initially when j takes the value zero, we will insert the value at index zero into this dictionary
or hash table.
So we will add one to this hash table.
And then when we come over here j has the value one.
So the value in the numb's array at index one is one.
And because one is already there in the hash table or the dictionary because that's what we did over
here.
Right.
So the hash table already has a value of one therefore because over here, because it's a repetition
of the value, we will not go deeper in this branch.
So if one is in the hash table we prune this branch and we go to the next branch and we proceed with
j is equal to two.
So this is how we can avoid this problem and solve this question.
So let's walk through the code and see what happens.
So at this point when j is equal to one we see that this value which is one is already there in the
dictionary or the hash table.
And therefore this branch is pruned.
And we come to this branch over here where j is two and we get 211 by swapping the values at index zero
and two.
Now let's proceed over here.
When I is equal to zero j is equal to zero.
We swap the elements.
We get one, one, two, and then we recursively call the same function the helper function again.
And at this point I is going to be equal to one.
And when I is equal to one, j will take the values from 1 to 2.
So again over here we have 012.
Now initially I is equal to one j is equal to one.
So we are just swapping the element at index one with the element at index one.
So we get 112 itself.
And then I is going to be equal to one.
And j is going to be equal to two.
So these two elements will be swapped.
And we get 121.
Now let's see what happens over here.
This branch anyway was pruned.
So in this branch when we get 211 we'll recursively call the helper function.
Again we will pass I is equal to one.
And when I is equal to one j will take the values from 1 to 2.
So initially I is equal to one j is equal to one.
So this over here does not change.
We get 211 itself.
But when it comes to the next branch over here and I is equal to one, j is equal to two.
Notice that when j is equal to one, the value one would have been added in the dictionary or the hash
table for this particular instance.
Right.
For this particular instance.
Now in this instance, the hash table over here when j is equal to one, would have added this value
over here one to it.
And when j is equal to two it will see that this value over here which is one.
Is already there in the hash table.
So we will not proceed in this branch and this would be pruned.
Now it's necessary to do that because if you don't do that we would again get 211 over here, which
is a repetition.
And we don't want repetitions.
We only want unique permutations.
So this again is going to be pruned through the same methodology that we have discussed.
And finally over here this will recursively call the same helper function again.
And I would be equal to two.
And at that point we would have hit the base case.
And this instance of the Nums array will be added to the results array.
Similarly this also gets added and this also gets added.
So you can see we were able to eliminate duplicates.
And we are getting the three unique permutations which are available for this particular input array.