Welcome back.
Let's now discuss a blueprint which you can use to solve any backtracking coding interview question.
Now this blueprint is a very powerful tool and it will help you solve any backtracking coding interview
question.
So let's get started.
Now we have discussed that backtracking is just controlled recursion, and where changes to the state
of the problem are made in place.
Now let's use this definition of backtracking to come up with our blueprint.
And let's go ahead and write the pseudocode for the blueprint that we will use in solving coding interview
questions in the future videos.
First of all, backtracking, as is mentioned over here is a recursive technique.
So let's go ahead and incorporate that into our pseudocode.
So let's say we have a function.
And let me just call it helper over here.
And we call the helper function.
All right.
So that's recursion.
And because we are dealing with recursion we do need a base condition.
Now, the base condition for backtracking is that if the problem at hand is solved, we either return
the solution or we save the solution or print the solution as the need of the coding question at hand
is.
So that's the base condition.
Now let's proceed.
The next thing that you can notice over here is that we will be modifying the state of the problem.
And we need to do this because there would be multiple choices that are available.
And we need to build our solution step by step by making choices.
So let's incorporate this into our pseudocode.
So I can say let me have a for loop over here for choice in choices.
And I'll take each choice I'll choose or make that choice.
And then call the same helper function recursively to go ahead and make the next choice.
Proceeding.
Let's take again a look at the definition of backtracking that we have over here.
It says controlled recursion.
So let's build this into our pseudocode.
So controlled recursion means that whenever a path does not lead to a solution we will abandon that
path.
So let's build that into our pseudocode.
So I can say if is valid choice then only I choose it.
So I have for choice in choices.
So I'm considering each choice and only if a choice is valid.
And again we have to write this function and it will be varying based on the question at hand and based
on the constraints which are given to us.
But if this returns true, then we will make that choice, and we will again recursively call the same
helper function.
So we have incorporated this as well into our pseudocode.
So let's proceed now.
And again let's take a look at what is remaining in the definition over here.
It says changes are made in place or passed by reference is used.
So because we are making changes in place whenever we come out of this helper function, and that will
happen when we have encountered a situation where we can't go deeper because the path is not leading
to a solution.
And when that happens, we have to come back and we have to revert this choice that we have made.
So let's write that over here.
Revert the choice.
Let's try once more.
Understand this part, because this may be confusing for a few students.
So let me make some space over here.
And let's again take the Sudoku problem that we discussed.
So we had the option to choose three, 5 or 8 over here.
We initially chose three.
So that's this part over here.
Choose.
And then we recursively call the same function to proceed and fill the next empty spaces.
So whenever we encountered that there was no more point in proceeding further that path, we had to
come back and we had to remove this three, which is what happens in reverse choice.
And again, we had to do this because we were not dealing with the copy of this board, but rather we
were making changes to the state of the problem in place.
We will see the full solution for this coding interview question in a later video, but over here,
we're just using this to analyze this part over here.
So what happens is first we have the choose line over here.
That's fill three.
And then when we identified that there was no more point to continue down this path, we had to come
back and remove three.
So the coming back was handled by recursion itself.
But removing three is the backtracking step.
And that's this line over here which is reverse choice.
So this line over here is the backtracking step.
And after we removed three we tried to fill the next possibility which was five.
So again that that would be handled by the for loop.
So we would come to the next choice and we will see whether that's valid.
And if it's valid we will choose it.
And we will recursively call the helper function again to proceed to the next empty space and go down
the path till we have solved the problem at hand.
And again notice this fill five over here.
This step over here happens when with three we were not able to get the solution.
So the reverting happens only when this function over here returns.
And it will come back over here.
When we see that there is no point in continuing down that path.
And at that point we have to revert the choice and then go to other choices which are available and
see if there is something else that fits the question.
So we have developed this blueprint which we can use to solve any backtracking question.
Now one more thing to note over here.
The for loop over here to make choices is particularly suitable when we have multiple possible choices,
like the case of the Sudoku board.
So we had choices like one, two, three, etc. up to nine.
So nine choices were possible for each empty cell.
Now there are some questions where you may have limited choices.
Like for example, you could just exclude something or include something.
So in these type of questions you will see that there is no need for a for loop.
And we can just write down the two possibilities.
Like for example, in the power set problem or the subsets problem, we will have an exclude choice
and an include choice.
Again, we will see this in great detail in a future video.
But over here we have successfully developed a blueprint for solving any backtracking coding interview
question.