Welcome back.
Let's now go ahead and write the pseudocode for the approach that we have discussed.
And for this let's also make use of the backtracking blueprint that we had previously discussed.
So let's get started.
We would need a helper function.
And probably let's just call it perm.
And this function will be called once.
And again it's going to be a recursive solution.
So let's go ahead and first write the base case.
As we have discussed over here when I was equal to two, it's at that point that J also would just be
two and there's no point in going ahead.
So we would make a copy of that particular instance and add it to the results array.
So that would be our base case.
So if I is equal to the length minus one the length is three.
Length minus one will give us the last index.
So when I is equal to length minus one add it to the results array.
So this is going to be our base case.
Now let's proceed.
The next part over here is for choice in choices.
So what are the different choices that we have over here?
So as we've seen over here, when I is equal to zero, the different choices for J was zero one and
two.
So the choices are for j to take the values from I to length minus one.
So for j is equal to I to length minus one.
And then over here the next part in our blueprint was we need to check whether that particular choice
is valid or not.
But in this case, because we are just finding all the permutations, all these are actually valid cases,
right.
So J taking zero, 1 or 2, all of these are valid.
So we don't need to check this in this question.
All right, because everything is valid.
So let's proceed.
Now, if things are valid, we need to proceed to this part of the blueprint where we make a choice,
which in our case is swapping the elements at I and J, and then recursively call the same function
again, and then revert the changes for the backtracking step.
So let's write that in our pseudocode.
So making the choice is swapping the elements at index I and j.
And then we are recursively calling the function again passing an index which is I plus one a higher
index.
Because over here I was zero.
Then when we recursively call it we want to pass I equal to one.
And over here when we again recursively call the function we want to pass I is equal to two.
So that's why over here the input parameter is I plus one.
And once we are out of this we want to swap the numbers at index I and j again back.
Because again we are implementing a backtracking solution where changes are made in place.
So this is going to be the backtracking step.
All right.
So we have discussed the pseudocode.
We have successfully written the pseudocode using the blueprint that we have discussed previously.
Let's now trace how the algorithm would solve this, because when we came up with the recursion tree,
we drew it out in a more intuitive manner so that we could easily understand it.
But now let's see how the algorithm would approach it.
So initially we would call the perm function.
And at this point I is going to be equal to zero.
And then this is going to call the perm function recursively with I equal to one.
So over here I is zero and j is zero.
And over here I is one and j is one.
And then it would again call the perm function recursively, at which point I is going to be equal to
two.
And when I is equal to two we will hit the base case.
So this over here is going to get added to the results array.
The final array that we will be returning which has all the permutations.
And after that it would just return.
So when it returns we would again come over here and we would come to this line over here where we again
swap the elements at one and one, and we will be back over here.
Now let's trace this part over here to understand it in a better manner.
Because over here, even though we did some swaps, the array does not change, right?
Because we were swapping zero with zero and one with one.
So once we are back over here and we call the perm function recursively, and at this point I is going
to be equal to one, but j is going to be equal to two.
Okay.
So we're going to swap the elements at one and two.
And 1 to 3 becomes 132.
And again it will call the function perm recursively.
And I will be equal to two.
And we will add 132 as well to our results array.
So at this .123 and 132 gets added.
But then notice that once this is done it's very important to do the backtracking step where we again
swap the.
Elements at index one and two.
So this is index one.
This is index two.
By doing this the nums array again changes from one three 2 to 1 two three.
Now, this is important because over here, when we want to swap the elements at index zero and one,
we have to ensure that we are starting with the Numb's array in this manner itself one two, three so
that when we swap the elements at index zero and one, this changes to two one, three.
So this is why the backtracking step is very important.
So next we come over here.
And then we come over here.
We add this to the results array.
Again we come back.
So when we backtrack again over here we can't see it.
But it's to reverse the change.
Revert the change that we did.
So again we come over here notice 213 changes to 231.
We add this to our results array.
And then we revert the changes so that 231 again becomes 213.
And we come back again when we come back over here 213 changes to 123.
This is again important notice because if we did not change this two back to one, two, three, then
this would not work, right?
But because of backtracking again at this point the Numb's array becomes one two, three.
And when we swap the elements at index zero and two, it changes to three two, one.
So this is how the backtracking algorithm works.
And notice that the changes to the Numb's array are made in place over here.