What makes backtracking different from just pruned recursion is that in backtracking, changes to the
state of the problem are made in place, or in other words, the input is passed by reference and we
are not making a copy of the input.
Now again, let's quickly discuss this and try to solidify this understanding about backtracking.
So in backtracking, as we've discussed, the state of the problem is modified in place.
Now for this, let's take an example to understand again what we mean with this.
So let's say we have a question at hand where we need to find all the permutations of a string.
Now again, if the string that is given to us is a, b, c, then all the permutations of this string
over here would be a, b, c, acb, BAC, BCA, C, A, b, and CBA.
So these are the six permutations of this string over here.
Now we discussed this question in a future video in detail.
But over here let's just use this to understand that in backtracking changes are made in place.
Now to solve this question and to arrive at this answer, we could take two approaches.
In approach one, we could create new arrays or strings and get all the permutations.
Now what do I mean with this?
Probably I could initially build a new array with just a.
And on top of that I could build the second layer where I append b to it, and then I can append c to
it.
So this would be one solution.
Similarly, let's say initially I appended a right.
So I have these two.
So in the second layer I append b in one case, and in the other case I append c to that array.
And then I append c over here and I append b over here.
And the difference is that these two are new arrays.
Or strings.
So this is one approach.
The second approach, which involves backtracking, is that I could get this answer by making changes
in place without creating a new array or string each time.
For example, if ABC is the input which is given to me, I could get c b a, which is one of the solutions
by just swapping the position of a and c.
Notice that if I swap these two.
I will get CBA and then I could just make a copy of this, put it to the answer array, which I finally
have to return, and then again swap A and C back to get back to ABC.
So when I take this approach, which is the backtracking approach, notice that I am not creating a
new array.
I am finding the solutions by making changes in place in memory.
Okay, so I am not allocating memory to create a new array.
I am using the same memory, but I'm just making swaps for example when it comes to this solution over
here.
So changes are made in place.
And for example I have ABC, I swap A and C and I get CBA.
So this is one of the solutions.
So I make a copy of this, put it into the results array.
And then I again swap C and A to get back to ABC.
Now I can just swap A and B.
If I do that I will get b a c right and b a c.
Notice is also one of the solutions.
So I have back, I make a copy of this and put it in the results array.
And after I'm done with this I again swap A and B to get back to ABC.
So in this way I am not creating new arrays or strings.
I am using the same array which is given to me.
I am making changes in place and this is another important characteristic about backtracking.
So backtracking is just controlled recursion where changes to the state of the problem are made in place.