1 00:00:00,480 --> 00:00:08,850 What makes backtracking different from just pruned recursion is that in backtracking, changes to the 2 00:00:08,850 --> 00:00:17,310 state of the problem are made in place, or in other words, the input is passed by reference and we 3 00:00:17,310 --> 00:00:19,440 are not making a copy of the input. 4 00:00:19,470 --> 00:00:25,950 Now again, let's quickly discuss this and try to solidify this understanding about backtracking. 5 00:00:25,950 --> 00:00:32,400 So in backtracking, as we've discussed, the state of the problem is modified in place. 6 00:00:32,400 --> 00:00:37,620 Now for this, let's take an example to understand again what we mean with this. 7 00:00:38,890 --> 00:00:46,060 So let's say we have a question at hand where we need to find all the permutations of a string. 8 00:00:46,090 --> 00:00:52,090 Now again, if the string that is given to us is a, b, c, then all the permutations of this string 9 00:00:52,090 --> 00:00:58,240 over here would be a, b, c, acb, BAC, BCA, C, A, b, and CBA. 10 00:00:58,330 --> 00:01:02,860 So these are the six permutations of this string over here. 11 00:01:02,890 --> 00:01:07,300 Now we discussed this question in a future video in detail. 12 00:01:07,300 --> 00:01:15,160 But over here let's just use this to understand that in backtracking changes are made in place. 13 00:01:15,190 --> 00:01:22,030 Now to solve this question and to arrive at this answer, we could take two approaches. 14 00:01:22,540 --> 00:01:30,340 In approach one, we could create new arrays or strings and get all the permutations. 15 00:01:30,370 --> 00:01:31,900 Now what do I mean with this? 16 00:01:31,900 --> 00:01:36,520 Probably I could initially build a new array with just a. 17 00:01:36,520 --> 00:01:43,870 And on top of that I could build the second layer where I append b to it, and then I can append c to 18 00:01:43,870 --> 00:01:43,990 it. 19 00:01:43,990 --> 00:01:45,700 So this would be one solution. 20 00:01:45,730 --> 00:01:48,700 Similarly, let's say initially I appended a right. 21 00:01:48,700 --> 00:01:50,350 So I have these two. 22 00:01:50,380 --> 00:01:56,230 So in the second layer I append b in one case, and in the other case I append c to that array. 23 00:01:56,230 --> 00:01:59,680 And then I append c over here and I append b over here. 24 00:01:59,680 --> 00:02:03,940 And the difference is that these two are new arrays. 25 00:02:05,100 --> 00:02:05,760 Or strings. 26 00:02:05,760 --> 00:02:07,830 So this is one approach. 27 00:02:07,860 --> 00:02:16,800 The second approach, which involves backtracking, is that I could get this answer by making changes 28 00:02:16,800 --> 00:02:21,810 in place without creating a new array or string each time. 29 00:02:21,810 --> 00:02:30,510 For example, if ABC is the input which is given to me, I could get c b a, which is one of the solutions 30 00:02:30,510 --> 00:02:35,430 by just swapping the position of a and c. 31 00:02:35,460 --> 00:02:37,620 Notice that if I swap these two. 32 00:02:38,210 --> 00:02:45,500 I will get CBA and then I could just make a copy of this, put it to the answer array, which I finally 33 00:02:45,500 --> 00:02:50,870 have to return, and then again swap A and C back to get back to ABC. 34 00:02:51,110 --> 00:02:58,670 So when I take this approach, which is the backtracking approach, notice that I am not creating a 35 00:02:58,670 --> 00:02:59,480 new array. 36 00:02:59,480 --> 00:03:05,150 I am finding the solutions by making changes in place in memory. 37 00:03:05,150 --> 00:03:08,270 Okay, so I am not allocating memory to create a new array. 38 00:03:08,270 --> 00:03:14,750 I am using the same memory, but I'm just making swaps for example when it comes to this solution over 39 00:03:14,750 --> 00:03:15,140 here. 40 00:03:15,140 --> 00:03:18,110 So changes are made in place. 41 00:03:18,110 --> 00:03:24,710 And for example I have ABC, I swap A and C and I get CBA. 42 00:03:24,950 --> 00:03:26,870 So this is one of the solutions. 43 00:03:26,870 --> 00:03:30,470 So I make a copy of this, put it into the results array. 44 00:03:30,470 --> 00:03:35,810 And then I again swap C and A to get back to ABC. 45 00:03:36,560 --> 00:03:39,530 Now I can just swap A and B. 46 00:03:39,560 --> 00:03:43,910 If I do that I will get b a c right and b a c. 47 00:03:43,940 --> 00:03:46,790 Notice is also one of the solutions. 48 00:03:46,790 --> 00:03:51,740 So I have back, I make a copy of this and put it in the results array. 49 00:03:51,740 --> 00:03:57,620 And after I'm done with this I again swap A and B to get back to ABC. 50 00:03:57,620 --> 00:04:01,580 So in this way I am not creating new arrays or strings. 51 00:04:01,580 --> 00:04:04,370 I am using the same array which is given to me. 52 00:04:04,370 --> 00:04:10,730 I am making changes in place and this is another important characteristic about backtracking. 53 00:04:10,730 --> 00:04:18,140 So backtracking is just controlled recursion where changes to the state of the problem are made in place.