1
00:00:00,110 --> 00:00:03,440
Let's now get into the code for solving permutations two.

2
00:00:03,710 --> 00:00:08,210
Now we have already written the code for permutations one previously.

3
00:00:08,210 --> 00:00:11,150
And over here that's just going to be a slight tweak.

4
00:00:11,150 --> 00:00:12,410
So let's get into it.

5
00:00:12,410 --> 00:00:14,210
So we will need a variable.

6
00:00:14,210 --> 00:00:18,140
Let's just call it rest which would be the results array okay.

7
00:00:18,140 --> 00:00:20,390
And finally we will be returning rest.

8
00:00:23,390 --> 00:00:23,870
All right.

9
00:00:23,870 --> 00:00:26,150
And this is going to be a recursive solution.

10
00:00:26,150 --> 00:00:28,430
So we will need a helper function.

11
00:00:28,430 --> 00:00:30,710
Let me just call it permutations.

12
00:00:31,250 --> 00:00:35,450
And to this function we will be passing a particular index.

13
00:00:35,450 --> 00:00:39,440
Now this is pretty similar to what we have done for permutations one okay.

14
00:00:39,440 --> 00:00:42,980
And we also have to call this function for the first time.

15
00:00:42,980 --> 00:00:47,000
And at this point we will be passing the index zero to it.

16
00:00:47,000 --> 00:00:48,620
So no change so far.

17
00:00:48,650 --> 00:00:54,590
Now inside the permutations function we will have to write the base case as well as the recursive case.

18
00:00:56,090 --> 00:01:03,620
Now the base case is if index is the last valid index, then we'll just make a copy of the particular

19
00:01:03,620 --> 00:01:05,990
instance of numb's and we will push it to rest.

20
00:01:05,990 --> 00:01:10,310
And that was the same base case which we had written for permutations one as well.

21
00:01:10,310 --> 00:01:12,200
So no change over there as well.

22
00:01:12,200 --> 00:01:21,860
So if index is equal to numb's dot length minus one, then we'll just make a copy of Numb's and push

23
00:01:21,860 --> 00:01:22,700
it to rest.

24
00:01:24,680 --> 00:01:25,280
All right.

25
00:01:25,280 --> 00:01:26,450
And we can return.

26
00:01:26,780 --> 00:01:31,970
So we are basically returning back from that particular branch on the recursive tree.

27
00:01:32,630 --> 00:01:36,500
Now if this is not the case then again we would need another variable.

28
00:01:36,500 --> 00:01:46,370
So I can say for where j is equal to index and j will take the values from index up to the last valid

29
00:01:46,370 --> 00:01:48,080
index in the numb's array.

30
00:01:48,770 --> 00:01:49,310
Okay.

31
00:01:52,120 --> 00:01:55,150
Now, what is it that we had previously written over here?

32
00:01:55,150 --> 00:01:58,630
We would swap the values at index I and j.

33
00:01:58,630 --> 00:02:09,130
So we had written numb's I comma Numb's j is equal to numb's j comma Numb's I.

34
00:02:09,130 --> 00:02:13,300
And we had made a recursive call to the helper function.

35
00:02:13,300 --> 00:02:15,220
So permutations index plus one.

36
00:02:15,220 --> 00:02:20,140
And again we had the backtracking step which is to revert the change that we just now did.

37
00:02:20,140 --> 00:02:23,470
And again over here we don't have I we have used index.

38
00:02:23,470 --> 00:02:26,680
So we have to write index over here and over here.

39
00:02:27,400 --> 00:02:29,380
And we have to revert the change.

40
00:02:29,380 --> 00:02:42,070
So again we can say numb's index comma Numb's j is equal to numb's j comma Numb's index.

41
00:02:42,700 --> 00:02:43,240
Okay.

42
00:02:43,240 --> 00:02:46,210
So this is what we had written for permutations one.

43
00:02:46,210 --> 00:02:51,190
But the change that we have to do over here, as we have discussed in the previous video, is that for

44
00:02:51,190 --> 00:02:58,300
a particular value of index, we will not take the case where numb's at j is repeating.

45
00:02:58,300 --> 00:02:58,690
Okay.

46
00:02:58,690 --> 00:03:03,010
So for example, at this particular index, like let us say index has a particular value.

47
00:03:03,010 --> 00:03:07,510
And let's say J is getting a particular value for a particular index.

48
00:03:07,510 --> 00:03:11,230
And if that value is repeating then we will prune that branch.

49
00:03:11,230 --> 00:03:13,930
So that's what we have discussed in detail in the previous video.

50
00:03:13,930 --> 00:03:17,080
And to implement this let's use a hash table.

51
00:03:17,200 --> 00:03:24,610
And before we go ahead and do these operations we will check whether numb's and J is in the hash table

52
00:03:24,610 --> 00:03:25,300
or not.

53
00:03:25,300 --> 00:03:25,720
Okay.

54
00:03:25,720 --> 00:03:27,460
So over here let me do that.

55
00:03:27,460 --> 00:03:33,670
So if not hash numb's at J then we proceed with these steps which we have over here.

56
00:03:36,630 --> 00:03:42,690
And if Numb's AJ is not in the hash table, we'll also have to add it to the hash table over here.

57
00:03:42,690 --> 00:03:47,820
So I can say hash numb's j is equal to one.

58
00:03:47,970 --> 00:03:48,420
Okay.

59
00:03:48,420 --> 00:03:53,490
So we're just adding it to the hash table so that next time like let's say j takes another value.

60
00:03:53,490 --> 00:03:58,980
And again numb's at j at that point is equal to the value numb's at j has at this point.

61
00:03:58,980 --> 00:04:05,160
Then that particular value will already be there in the hash table, and therefore these lines of code

62
00:04:05,160 --> 00:04:06,420
will not be executed.

63
00:04:06,420 --> 00:04:10,680
And in this way we are pruning that particular branch in the recursive tree.

64
00:04:10,770 --> 00:04:11,670
So that's it.

65
00:04:11,670 --> 00:04:15,540
Now let's go ahead and run this code and see if it's passing all the test cases.

66
00:04:19,150 --> 00:04:21,940
And you can see that it's passing all the test cases.

67
00:04:21,940 --> 00:04:27,730
Also, remember to make use of the user logs which are provided for each test case in case you're stuck

68
00:04:27,730 --> 00:04:30,430
at some place and you want to debug your code.