1 00:00:00,020 --> 00:00:00,800 Welcome back. 2 00:00:01,100 --> 00:00:09,560 Let's now discuss a blueprint which you can use to solve any backtracking coding interview question. 3 00:00:09,590 --> 00:00:18,050 Now this blueprint is a very powerful tool and it will help you solve any backtracking coding interview 4 00:00:18,050 --> 00:00:18,680 question. 5 00:00:18,680 --> 00:00:20,330 So let's get started. 6 00:00:20,720 --> 00:00:28,940 Now we have discussed that backtracking is just controlled recursion, and where changes to the state 7 00:00:28,940 --> 00:00:31,550 of the problem are made in place. 8 00:00:31,550 --> 00:00:36,560 Now let's use this definition of backtracking to come up with our blueprint. 9 00:00:36,560 --> 00:00:43,580 And let's go ahead and write the pseudocode for the blueprint that we will use in solving coding interview 10 00:00:43,580 --> 00:00:45,950 questions in the future videos. 11 00:00:45,980 --> 00:00:52,520 First of all, backtracking, as is mentioned over here is a recursive technique. 12 00:00:52,520 --> 00:00:56,540 So let's go ahead and incorporate that into our pseudocode. 13 00:00:56,540 --> 00:00:58,490 So let's say we have a function. 14 00:00:58,700 --> 00:01:01,340 And let me just call it helper over here. 15 00:01:01,340 --> 00:01:03,740 And we call the helper function. 16 00:01:03,740 --> 00:01:04,370 All right. 17 00:01:04,370 --> 00:01:05,810 So that's recursion. 18 00:01:05,810 --> 00:01:11,300 And because we are dealing with recursion we do need a base condition. 19 00:01:12,050 --> 00:01:20,090 Now, the base condition for backtracking is that if the problem at hand is solved, we either return 20 00:01:20,090 --> 00:01:27,950 the solution or we save the solution or print the solution as the need of the coding question at hand 21 00:01:27,980 --> 00:01:28,430 is. 22 00:01:28,430 --> 00:01:30,350 So that's the base condition. 23 00:01:30,380 --> 00:01:31,760 Now let's proceed. 24 00:01:31,760 --> 00:01:38,120 The next thing that you can notice over here is that we will be modifying the state of the problem. 25 00:01:38,120 --> 00:01:44,330 And we need to do this because there would be multiple choices that are available. 26 00:01:44,330 --> 00:01:50,180 And we need to build our solution step by step by making choices. 27 00:01:50,180 --> 00:01:53,930 So let's incorporate this into our pseudocode. 28 00:01:53,930 --> 00:02:00,050 So I can say let me have a for loop over here for choice in choices. 29 00:02:00,050 --> 00:02:04,100 And I'll take each choice I'll choose or make that choice. 30 00:02:04,100 --> 00:02:11,780 And then call the same helper function recursively to go ahead and make the next choice. 31 00:02:11,780 --> 00:02:12,740 Proceeding. 32 00:02:12,740 --> 00:02:17,390 Let's take again a look at the definition of backtracking that we have over here. 33 00:02:17,390 --> 00:02:19,760 It says controlled recursion. 34 00:02:19,760 --> 00:02:22,790 So let's build this into our pseudocode. 35 00:02:22,790 --> 00:02:30,770 So controlled recursion means that whenever a path does not lead to a solution we will abandon that 36 00:02:30,770 --> 00:02:31,310 path. 37 00:02:31,700 --> 00:02:34,490 So let's build that into our pseudocode. 38 00:02:34,490 --> 00:02:40,070 So I can say if is valid choice then only I choose it. 39 00:02:40,070 --> 00:02:42,350 So I have for choice in choices. 40 00:02:42,350 --> 00:02:46,940 So I'm considering each choice and only if a choice is valid. 41 00:02:46,940 --> 00:02:53,120 And again we have to write this function and it will be varying based on the question at hand and based 42 00:02:53,120 --> 00:02:55,070 on the constraints which are given to us. 43 00:02:55,070 --> 00:03:02,540 But if this returns true, then we will make that choice, and we will again recursively call the same 44 00:03:02,540 --> 00:03:03,440 helper function. 45 00:03:03,440 --> 00:03:07,220 So we have incorporated this as well into our pseudocode. 46 00:03:07,220 --> 00:03:08,480 So let's proceed now. 47 00:03:08,480 --> 00:03:12,530 And again let's take a look at what is remaining in the definition over here. 48 00:03:12,530 --> 00:03:17,750 It says changes are made in place or passed by reference is used. 49 00:03:17,750 --> 00:03:25,970 So because we are making changes in place whenever we come out of this helper function, and that will 50 00:03:25,970 --> 00:03:33,020 happen when we have encountered a situation where we can't go deeper because the path is not leading 51 00:03:33,050 --> 00:03:33,980 to a solution. 52 00:03:33,980 --> 00:03:41,480 And when that happens, we have to come back and we have to revert this choice that we have made. 53 00:03:41,480 --> 00:03:42,920 So let's write that over here. 54 00:03:42,920 --> 00:03:44,240 Revert the choice. 55 00:03:44,900 --> 00:03:46,160 Let's try once more. 56 00:03:46,160 --> 00:03:51,050 Understand this part, because this may be confusing for a few students. 57 00:03:51,050 --> 00:03:53,120 So let me make some space over here. 58 00:03:53,860 --> 00:03:58,000 And let's again take the Sudoku problem that we discussed. 59 00:03:58,000 --> 00:04:02,590 So we had the option to choose three, 5 or 8 over here. 60 00:04:02,860 --> 00:04:04,480 We initially chose three. 61 00:04:04,480 --> 00:04:06,460 So that's this part over here. 62 00:04:06,460 --> 00:04:07,030 Choose. 63 00:04:07,030 --> 00:04:13,870 And then we recursively call the same function to proceed and fill the next empty spaces. 64 00:04:13,870 --> 00:04:21,070 So whenever we encountered that there was no more point in proceeding further that path, we had to 65 00:04:21,070 --> 00:04:27,940 come back and we had to remove this three, which is what happens in reverse choice. 66 00:04:27,940 --> 00:04:34,420 And again, we had to do this because we were not dealing with the copy of this board, but rather we 67 00:04:34,420 --> 00:04:38,260 were making changes to the state of the problem in place. 68 00:04:38,740 --> 00:04:45,160 We will see the full solution for this coding interview question in a later video, but over here, 69 00:04:45,160 --> 00:04:48,220 we're just using this to analyze this part over here. 70 00:04:48,220 --> 00:04:52,180 So what happens is first we have the choose line over here. 71 00:04:52,180 --> 00:04:53,770 That's fill three. 72 00:04:54,010 --> 00:05:00,520 And then when we identified that there was no more point to continue down this path, we had to come 73 00:05:00,520 --> 00:05:02,770 back and remove three. 74 00:05:02,770 --> 00:05:06,760 So the coming back was handled by recursion itself. 75 00:05:06,760 --> 00:05:10,060 But removing three is the backtracking step. 76 00:05:10,060 --> 00:05:13,030 And that's this line over here which is reverse choice. 77 00:05:13,030 --> 00:05:17,620 So this line over here is the backtracking step. 78 00:05:17,620 --> 00:05:23,470 And after we removed three we tried to fill the next possibility which was five. 79 00:05:23,470 --> 00:05:26,290 So again that that would be handled by the for loop. 80 00:05:26,290 --> 00:05:30,010 So we would come to the next choice and we will see whether that's valid. 81 00:05:30,010 --> 00:05:31,960 And if it's valid we will choose it. 82 00:05:31,960 --> 00:05:38,590 And we will recursively call the helper function again to proceed to the next empty space and go down 83 00:05:38,590 --> 00:05:41,560 the path till we have solved the problem at hand. 84 00:05:41,560 --> 00:05:44,740 And again notice this fill five over here. 85 00:05:44,740 --> 00:05:50,950 This step over here happens when with three we were not able to get the solution. 86 00:05:50,950 --> 00:05:55,690 So the reverting happens only when this function over here returns. 87 00:05:55,690 --> 00:05:57,520 And it will come back over here. 88 00:05:57,520 --> 00:06:01,630 When we see that there is no point in continuing down that path. 89 00:06:01,630 --> 00:06:08,830 And at that point we have to revert the choice and then go to other choices which are available and 90 00:06:08,830 --> 00:06:11,620 see if there is something else that fits the question. 91 00:06:11,620 --> 00:06:18,070 So we have developed this blueprint which we can use to solve any backtracking question. 92 00:06:18,490 --> 00:06:20,560 Now one more thing to note over here. 93 00:06:20,560 --> 00:06:28,060 The for loop over here to make choices is particularly suitable when we have multiple possible choices, 94 00:06:28,060 --> 00:06:30,280 like the case of the Sudoku board. 95 00:06:30,280 --> 00:06:33,820 So we had choices like one, two, three, etc. up to nine. 96 00:06:33,820 --> 00:06:37,930 So nine choices were possible for each empty cell. 97 00:06:37,930 --> 00:06:42,790 Now there are some questions where you may have limited choices. 98 00:06:42,970 --> 00:06:47,890 Like for example, you could just exclude something or include something. 99 00:06:47,890 --> 00:06:53,230 So in these type of questions you will see that there is no need for a for loop. 100 00:06:53,230 --> 00:06:56,080 And we can just write down the two possibilities. 101 00:06:56,080 --> 00:07:02,080 Like for example, in the power set problem or the subsets problem, we will have an exclude choice 102 00:07:02,080 --> 00:07:03,460 and an include choice. 103 00:07:03,460 --> 00:07:07,240 Again, we will see this in great detail in a future video. 104 00:07:07,240 --> 00:07:13,420 But over here we have successfully developed a blueprint for solving any backtracking coding interview 105 00:07:13,420 --> 00:07:14,080 question.