Welcome back.
We have discussed backtracking and developed a good understanding of this algorithmic approach and how
to use this to solve coding interview questions.
In this video, let's discuss how to identify whether backtracking can be used in solving a coding interview
question.
And let's also discuss how to identify that backtracking is not to be used in a particular coding interview
question.
Now first let's discuss when to use it.
Backtracking is especially useful when a problem requires you to explore every possible path.
It's especially useful when you need to identify all the solutions for a particular problem.
Let's say you need to find all the permutations of a string that is given to you.
Now in these questions, backtracking is very useful, but backtracking is not to be used for optimization
problems.
If you want to find the best, or the largest, or the smallest, or the maximum of something, probably
that question requires dynamic programming and not backtracking.
Now again we will discuss.
There are some dynamic programming questions where you can combine principles of dynamic programming
with backtracking, but more of that in a future video.
Over here we have discussed that whenever you have a question that asks you to find all the possible
solutions, probably you can use backtracking.
And again, it's not always the case.
There are some backtracking, coding, interview questions where you just need to find one solution,
like for example, the Sudoku solver.
But again, over there you have multiple choices and you want to explore all of those, and you want
to prune paths that don't lead to the solution.
So that again indicates that you can use backtracking to solve that particular coding interview question.