1
00:00:00,370 --> 00:00:01,570
Welcome back.

2
00:00:01,600 --> 00:00:07,360
Let's now go ahead and write the pseudocode for the approach that we have discussed.

3
00:00:07,360 --> 00:00:13,450
And again let's make use of the backtracking blueprint that we previously discussed.

4
00:00:13,450 --> 00:00:15,760
So we have the blueprint over here.

5
00:00:16,150 --> 00:00:20,920
This is the pseudocode that we have discussed for the permutations question.

6
00:00:20,920 --> 00:00:27,460
Now let's see how we have to slightly modify this to get to the approach that we have discussed over

7
00:00:27,460 --> 00:00:27,940
here.

8
00:00:27,940 --> 00:00:35,980
So the change that we need to do is that for each value of I, we need to check whether the value of

9
00:00:35,980 --> 00:00:39,010
J was already encountered or not.

10
00:00:39,010 --> 00:00:43,150
So for example, remember over here initially j is equal to zero.

11
00:00:43,180 --> 00:00:46,480
The value is one and then j is equal to one.

12
00:00:46,480 --> 00:00:47,980
Again the value is one.

13
00:00:47,980 --> 00:00:50,200
So these two values are the same.

14
00:00:50,200 --> 00:00:57,160
And because we were inserting values to the hash table or dictionary, we are able to identify that

15
00:00:57,160 --> 00:00:58,330
this is a repetition.

16
00:00:58,330 --> 00:00:59,770
And we skip this.

17
00:00:59,770 --> 00:01:02,050
And we proceed to the next branch.

18
00:01:02,050 --> 00:01:06,250
So for this we would need a hash table or a dictionary.

19
00:01:06,250 --> 00:01:10,810
So at this point let's say we declare it so hash is an empty object.

20
00:01:10,810 --> 00:01:17,860
And then before we do these three steps which is equivalent to going deeper on the recursion tree,

21
00:01:17,890 --> 00:01:23,770
we check whether numb's at j is in the hash table or not.

22
00:01:23,800 --> 00:01:30,580
Now, if it is not in the hash table first we will insert it to the hash table, and then we will proceed

23
00:01:30,580 --> 00:01:32,770
with these three steps over here.

24
00:01:32,770 --> 00:01:34,930
So this is how we can solve this.

25
00:01:35,320 --> 00:01:41,530
So notice over here in the permutations question we did not have an is valid over here.

26
00:01:41,530 --> 00:01:43,660
We did not have any is valid function.

27
00:01:43,660 --> 00:01:47,620
There was nothing to check over here because every choice was valid.

28
00:01:47,620 --> 00:01:55,090
But in this question we have a criteria to check whether the choice is valid or not, which is whether

29
00:01:55,090 --> 00:01:58,600
numb's at j is in the hash table or not.

30
00:01:58,600 --> 00:02:06,010
Now we proceed with choose and recursively calling the function and reverting the choice only if numb's

31
00:02:06,010 --> 00:02:08,770
at j is not in the hash table.

32
00:02:08,770 --> 00:02:12,880
So notice over here we have incorporated this as well in this approach.