1
00:00:00,170 --> 00:00:03,740
Let's now get into the code for solving the permutations question.

2
00:00:03,740 --> 00:00:08,060
So we have discussed the method that we are going to use in detail in the previous video.

3
00:00:08,060 --> 00:00:14,150
And as we have discussed, we will need a results array where we will be storing all the permutations

4
00:00:14,150 --> 00:00:15,800
as we get to a permutation.

5
00:00:15,800 --> 00:00:19,160
And finally we will be returning this okay.

6
00:00:19,160 --> 00:00:22,100
And this is going to be a recursive solution.

7
00:00:22,100 --> 00:00:24,260
So we are going to need a helper function.

8
00:00:24,260 --> 00:00:26,420
Let me just call it helper itself.

9
00:00:26,420 --> 00:00:30,770
And to this function we will be passing I or an index okay.

10
00:00:30,770 --> 00:00:32,600
And let's write the details later.

11
00:00:32,600 --> 00:00:38,090
But over here when we call this helper function for the first time, we will be passing the index zero

12
00:00:38,090 --> 00:00:42,260
okay, which is the first index of the numb's array which is given to us.

13
00:00:42,260 --> 00:00:45,440
Now let's go ahead and write the details of this helper function.

14
00:00:45,440 --> 00:00:51,020
So we will be both writing the base case as well as the recursive case.

15
00:00:52,870 --> 00:01:00,010
Now the base case would be the scenario where I, which is the index that is passed to the helper function,

16
00:01:00,010 --> 00:01:03,760
is equal to the last index of the Nums array.

17
00:01:03,760 --> 00:01:08,560
Because if that is the case, as we have discussed in the previous video, there is no value beyond

18
00:01:08,560 --> 00:01:08,740
it.

19
00:01:08,740 --> 00:01:13,990
So there is no point swapping the element at that particular index with anything else because there's

20
00:01:13,990 --> 00:01:15,010
nothing beyond it.

21
00:01:15,010 --> 00:01:23,590
So if I is equal to the last index, which is equal to n minus one, if n is the length of the numb's

22
00:01:23,590 --> 00:01:23,800
array.

23
00:01:23,800 --> 00:01:24,880
So let's write that over here.

24
00:01:24,880 --> 00:01:28,180
So let's say let n is equal to numb's dot length.

25
00:01:29,140 --> 00:01:34,810
So if this is the case and if I is equal to n minus one we would have hit the base case.

26
00:01:34,810 --> 00:01:36,910
So there is no more swapping to be done.

27
00:01:36,910 --> 00:01:44,260
And all that we need to do is we just need to make a copy of the current state of the Nums array and

28
00:01:44,260 --> 00:01:45,400
push it to us.

29
00:01:45,430 --> 00:01:47,590
Okay, so I can say rest or push.

30
00:01:48,220 --> 00:01:54,340
And over here we are going to make a copy of the Nums array at this particular state.

31
00:01:54,730 --> 00:01:59,020
And again, the reason why we need to do this is because this is a backtracking solution.

32
00:01:59,020 --> 00:02:03,490
So as we have discussed, we will be making changes to the state of the problem in place.

33
00:02:03,490 --> 00:02:08,020
So at a later stage, the way that the numb's array looks would be different.

34
00:02:08,020 --> 00:02:10,090
So that's why we are making a snapshot.

35
00:02:10,090 --> 00:02:15,370
Or we are making a copy of how the Numb's array looks at this particular point, and we are pushing

36
00:02:15,370 --> 00:02:16,660
it to the results array.

37
00:02:16,660 --> 00:02:18,310
And then we can just return.

38
00:02:18,460 --> 00:02:18,820
Okay.

39
00:02:18,820 --> 00:02:23,380
So we are stopping going further down that particular branch of the recursive tree.

40
00:02:23,380 --> 00:02:24,520
And we are returning.

41
00:02:24,520 --> 00:02:28,870
Now if this is not the case then we proceed to the recursive case.

42
00:02:28,870 --> 00:02:32,470
Now this is the case where I is not equal to n minus one.

43
00:02:32,470 --> 00:02:35,290
And in this case we will need another variable.

44
00:02:35,290 --> 00:02:36,550
Let's call it j.

45
00:02:36,550 --> 00:02:44,500
And j will take the values starting at I, and it will go up to the last valid index which is n minus

46
00:02:44,500 --> 00:02:45,550
one okay.

47
00:02:45,940 --> 00:02:50,050
And for each value of j we are going to do three things.

48
00:02:50,050 --> 00:02:54,970
First, we are going to swap the elements at index I and index j.

49
00:02:54,970 --> 00:03:03,550
So I can say numb's at I comma numb's j is equal to numb's at j comma numb's at I.

50
00:03:03,580 --> 00:03:09,730
Okay, so I have swapped these two elements and then we will go deeper down that particular branch of

51
00:03:09,730 --> 00:03:10,600
the recursive tree.

52
00:03:10,600 --> 00:03:13,720
So for that I will recursively call the helper function.

53
00:03:13,720 --> 00:03:16,360
And we will be passing I plus one to it.

54
00:03:16,360 --> 00:03:22,180
Now after we come back over here, that is after we have gone down all the way till the base case in

55
00:03:22,180 --> 00:03:25,990
that particular branch on the recursive tree, and we get back over here.

56
00:03:25,990 --> 00:03:29,110
Then we'll have to proceed and do the backtracking step.

57
00:03:30,100 --> 00:03:30,580
Okay.

58
00:03:30,580 --> 00:03:36,550
And remember this is important because we are making changes to the state of the problem in place,

59
00:03:36,550 --> 00:03:42,970
or we are changing numb's the Nums array itself to get the various permutations, and then to explore

60
00:03:42,970 --> 00:03:48,130
another branch in the recursive tree, we need to keep reverting the changes we have made.

61
00:03:48,130 --> 00:03:49,630
So that is what we are doing over here.

62
00:03:49,630 --> 00:04:00,190
So I can say numb's I comma numb's j is equal to numb's j comma Numb's I.

63
00:04:00,580 --> 00:04:07,630
Okay, so again we are reverting the changes that we made in this line of code over here.

64
00:04:07,630 --> 00:04:09,400
And this is the backtracking step.

65
00:04:09,700 --> 00:04:10,330
All right.

66
00:04:10,330 --> 00:04:11,290
So that's it.

67
00:04:11,290 --> 00:04:12,880
So this should solve the problem.

68
00:04:12,880 --> 00:04:17,350
Now let's go ahead and run this code and see if it's passing all the test cases.

69
00:04:18,370 --> 00:04:23,290
And you can see that it's passing all the test cases in case you're stuck and need help.

70
00:04:23,290 --> 00:04:27,280
Do make use of the user logs which are provided over here for every test case.