1 00:00:00,420 --> 00:00:01,560 Welcome back. 2 00:00:01,800 --> 00:00:06,930 Let's now go ahead and write the pseudocode for the approach that we have discussed. 3 00:00:06,930 --> 00:00:14,430 And for this let's also make use of the backtracking blueprint that we had previously discussed. 4 00:00:14,430 --> 00:00:16,020 So let's get started. 5 00:00:16,020 --> 00:00:17,850 We would need a helper function. 6 00:00:17,850 --> 00:00:20,790 And probably let's just call it perm. 7 00:00:20,790 --> 00:00:23,760 And this function will be called once. 8 00:00:23,760 --> 00:00:26,760 And again it's going to be a recursive solution. 9 00:00:26,760 --> 00:00:29,580 So let's go ahead and first write the base case. 10 00:00:29,580 --> 00:00:36,690 As we have discussed over here when I was equal to two, it's at that point that J also would just be 11 00:00:36,690 --> 00:00:39,540 two and there's no point in going ahead. 12 00:00:39,540 --> 00:00:44,520 So we would make a copy of that particular instance and add it to the results array. 13 00:00:44,520 --> 00:00:46,470 So that would be our base case. 14 00:00:46,470 --> 00:00:51,210 So if I is equal to the length minus one the length is three. 15 00:00:51,210 --> 00:00:53,880 Length minus one will give us the last index. 16 00:00:53,880 --> 00:00:58,620 So when I is equal to length minus one add it to the results array. 17 00:00:58,620 --> 00:01:00,990 So this is going to be our base case. 18 00:01:00,990 --> 00:01:02,460 Now let's proceed. 19 00:01:03,290 --> 00:01:06,860 The next part over here is for choice in choices. 20 00:01:06,860 --> 00:01:09,830 So what are the different choices that we have over here? 21 00:01:09,830 --> 00:01:16,370 So as we've seen over here, when I is equal to zero, the different choices for J was zero one and 22 00:01:16,370 --> 00:01:16,880 two. 23 00:01:17,000 --> 00:01:23,090 So the choices are for j to take the values from I to length minus one. 24 00:01:23,090 --> 00:01:26,630 So for j is equal to I to length minus one. 25 00:01:26,630 --> 00:01:33,320 And then over here the next part in our blueprint was we need to check whether that particular choice 26 00:01:33,320 --> 00:01:34,400 is valid or not. 27 00:01:34,400 --> 00:01:41,120 But in this case, because we are just finding all the permutations, all these are actually valid cases, 28 00:01:41,120 --> 00:01:41,480 right. 29 00:01:41,480 --> 00:01:44,960 So J taking zero, 1 or 2, all of these are valid. 30 00:01:44,960 --> 00:01:48,110 So we don't need to check this in this question. 31 00:01:49,270 --> 00:01:50,980 All right, because everything is valid. 32 00:01:50,980 --> 00:01:52,330 So let's proceed. 33 00:01:52,360 --> 00:01:58,870 Now, if things are valid, we need to proceed to this part of the blueprint where we make a choice, 34 00:01:58,870 --> 00:02:05,980 which in our case is swapping the elements at I and J, and then recursively call the same function 35 00:02:05,980 --> 00:02:10,030 again, and then revert the changes for the backtracking step. 36 00:02:10,030 --> 00:02:12,010 So let's write that in our pseudocode. 37 00:02:12,010 --> 00:02:16,810 So making the choice is swapping the elements at index I and j. 38 00:02:17,410 --> 00:02:24,430 And then we are recursively calling the function again passing an index which is I plus one a higher 39 00:02:24,430 --> 00:02:24,940 index. 40 00:02:24,940 --> 00:02:26,380 Because over here I was zero. 41 00:02:26,380 --> 00:02:30,220 Then when we recursively call it we want to pass I equal to one. 42 00:02:30,220 --> 00:02:36,130 And over here when we again recursively call the function we want to pass I is equal to two. 43 00:02:36,160 --> 00:02:40,300 So that's why over here the input parameter is I plus one. 44 00:02:40,300 --> 00:02:46,480 And once we are out of this we want to swap the numbers at index I and j again back. 45 00:02:46,480 --> 00:02:52,540 Because again we are implementing a backtracking solution where changes are made in place. 46 00:02:52,540 --> 00:02:55,540 So this is going to be the backtracking step. 47 00:02:57,390 --> 00:02:57,990 All right. 48 00:02:57,990 --> 00:03:00,510 So we have discussed the pseudocode. 49 00:03:00,510 --> 00:03:05,490 We have successfully written the pseudocode using the blueprint that we have discussed previously. 50 00:03:06,640 --> 00:03:12,760 Let's now trace how the algorithm would solve this, because when we came up with the recursion tree, 51 00:03:12,760 --> 00:03:17,740 we drew it out in a more intuitive manner so that we could easily understand it. 52 00:03:17,740 --> 00:03:20,650 But now let's see how the algorithm would approach it. 53 00:03:20,650 --> 00:03:24,190 So initially we would call the perm function. 54 00:03:24,190 --> 00:03:27,430 And at this point I is going to be equal to zero. 55 00:03:27,430 --> 00:03:33,310 And then this is going to call the perm function recursively with I equal to one. 56 00:03:33,310 --> 00:03:35,890 So over here I is zero and j is zero. 57 00:03:35,890 --> 00:03:39,130 And over here I is one and j is one. 58 00:03:39,130 --> 00:03:45,100 And then it would again call the perm function recursively, at which point I is going to be equal to 59 00:03:45,100 --> 00:03:45,670 two. 60 00:03:45,670 --> 00:03:48,760 And when I is equal to two we will hit the base case. 61 00:03:48,760 --> 00:03:53,350 So this over here is going to get added to the results array. 62 00:03:53,380 --> 00:03:57,310 The final array that we will be returning which has all the permutations. 63 00:03:57,310 --> 00:03:59,470 And after that it would just return. 64 00:03:59,470 --> 00:04:06,280 So when it returns we would again come over here and we would come to this line over here where we again 65 00:04:06,280 --> 00:04:09,730 swap the elements at one and one, and we will be back over here. 66 00:04:10,760 --> 00:04:15,920 Now let's trace this part over here to understand it in a better manner. 67 00:04:15,920 --> 00:04:20,360 Because over here, even though we did some swaps, the array does not change, right? 68 00:04:20,360 --> 00:04:23,360 Because we were swapping zero with zero and one with one. 69 00:04:23,360 --> 00:04:31,880 So once we are back over here and we call the perm function recursively, and at this point I is going 70 00:04:31,880 --> 00:04:36,530 to be equal to one, but j is going to be equal to two. 71 00:04:37,070 --> 00:04:37,550 Okay. 72 00:04:37,550 --> 00:04:40,340 So we're going to swap the elements at one and two. 73 00:04:40,340 --> 00:04:44,150 And 1 to 3 becomes 132. 74 00:04:44,150 --> 00:04:47,420 And again it will call the function perm recursively. 75 00:04:47,420 --> 00:04:49,010 And I will be equal to two. 76 00:04:49,010 --> 00:04:52,610 And we will add 132 as well to our results array. 77 00:04:52,610 --> 00:04:58,100 So at this .123 and 132 gets added. 78 00:04:58,100 --> 00:05:06,380 But then notice that once this is done it's very important to do the backtracking step where we again 79 00:05:06,380 --> 00:05:07,370 swap the. 80 00:05:07,940 --> 00:05:10,220 Elements at index one and two. 81 00:05:10,250 --> 00:05:11,390 So this is index one. 82 00:05:11,390 --> 00:05:12,500 This is index two. 83 00:05:12,530 --> 00:05:19,070 By doing this the nums array again changes from one three 2 to 1 two three. 84 00:05:20,070 --> 00:05:26,400 Now, this is important because over here, when we want to swap the elements at index zero and one, 85 00:05:26,400 --> 00:05:33,150 we have to ensure that we are starting with the Numb's array in this manner itself one two, three so 86 00:05:33,150 --> 00:05:38,610 that when we swap the elements at index zero and one, this changes to two one, three. 87 00:05:38,610 --> 00:05:42,450 So this is why the backtracking step is very important. 88 00:05:42,450 --> 00:05:44,340 So next we come over here. 89 00:05:45,320 --> 00:05:47,090 And then we come over here. 90 00:05:47,090 --> 00:05:49,430 We add this to the results array. 91 00:05:49,460 --> 00:05:50,810 Again we come back. 92 00:05:50,810 --> 00:05:54,650 So when we backtrack again over here we can't see it. 93 00:05:54,650 --> 00:05:56,780 But it's to reverse the change. 94 00:05:56,780 --> 00:05:58,160 Revert the change that we did. 95 00:05:58,160 --> 00:06:03,800 So again we come over here notice 213 changes to 231. 96 00:06:03,800 --> 00:06:05,840 We add this to our results array. 97 00:06:05,840 --> 00:06:11,330 And then we revert the changes so that 231 again becomes 213. 98 00:06:11,330 --> 00:06:17,690 And we come back again when we come back over here 213 changes to 123. 99 00:06:17,690 --> 00:06:23,450 This is again important notice because if we did not change this two back to one, two, three, then 100 00:06:23,450 --> 00:06:24,650 this would not work, right? 101 00:06:24,650 --> 00:06:30,110 But because of backtracking again at this point the Numb's array becomes one two, three. 102 00:06:30,110 --> 00:06:36,020 And when we swap the elements at index zero and two, it changes to three two, one. 103 00:06:36,020 --> 00:06:39,920 So this is how the backtracking algorithm works. 104 00:06:40,310 --> 00:06:45,710 And notice that the changes to the Numb's array are made in place over here.