1
00:00:00,110 --> 00:00:01,100
Welcome back.

2
00:00:01,100 --> 00:00:08,690
We have discussed backtracking and developed a good understanding of this algorithmic approach and how

3
00:00:08,690 --> 00:00:12,230
to use this to solve coding interview questions.

4
00:00:12,440 --> 00:00:20,120
In this video, let's discuss how to identify whether backtracking can be used in solving a coding interview

5
00:00:20,120 --> 00:00:20,690
question.

6
00:00:20,690 --> 00:00:28,340
And let's also discuss how to identify that backtracking is not to be used in a particular coding interview

7
00:00:28,340 --> 00:00:29,060
question.

8
00:00:29,060 --> 00:00:32,090
Now first let's discuss when to use it.

9
00:00:32,090 --> 00:00:40,790
Backtracking is especially useful when a problem requires you to explore every possible path.

10
00:00:41,440 --> 00:00:48,580
It's especially useful when you need to identify all the solutions for a particular problem.

11
00:00:48,580 --> 00:00:54,460
Let's say you need to find all the permutations of a string that is given to you.

12
00:00:54,460 --> 00:01:02,200
Now in these questions, backtracking is very useful, but backtracking is not to be used for optimization

13
00:01:02,200 --> 00:01:03,010
problems.

14
00:01:03,460 --> 00:01:11,080
If you want to find the best, or the largest, or the smallest, or the maximum of something, probably

15
00:01:11,080 --> 00:01:15,790
that question requires dynamic programming and not backtracking.

16
00:01:15,790 --> 00:01:17,350
Now again we will discuss.

17
00:01:17,350 --> 00:01:23,410
There are some dynamic programming questions where you can combine principles of dynamic programming

18
00:01:23,410 --> 00:01:27,160
with backtracking, but more of that in a future video.

19
00:01:27,160 --> 00:01:33,400
Over here we have discussed that whenever you have a question that asks you to find all the possible

20
00:01:33,400 --> 00:01:37,420
solutions, probably you can use backtracking.

21
00:01:37,420 --> 00:01:40,150
And again, it's not always the case.

22
00:01:40,150 --> 00:01:45,670
There are some backtracking, coding, interview questions where you just need to find one solution,

23
00:01:45,670 --> 00:01:47,800
like for example, the Sudoku solver.

24
00:01:47,800 --> 00:01:55,030
But again, over there you have multiple choices and you want to explore all of those, and you want

25
00:01:55,030 --> 00:01:57,670
to prune paths that don't lead to the solution.

26
00:01:57,670 --> 00:02:03,790
So that again indicates that you can use backtracking to solve that particular coding interview question.