1
00:00:00,080 --> 00:00:07,400
Let's now discuss an optimization that we can make to the approach that we previously discussed over

2
00:00:07,400 --> 00:00:07,760
here.

3
00:00:07,760 --> 00:00:11,480
For example, notice that k is equal to three.

4
00:00:11,480 --> 00:00:15,650
So every combination has to have a length of three.

5
00:00:15,650 --> 00:00:21,590
But in this branch over here where we are starting with the value three.

6
00:00:21,590 --> 00:00:25,160
And then the next value that we can include will be four.

7
00:00:27,730 --> 00:00:28,210
Right.

8
00:00:28,210 --> 00:00:30,850
So the next value that we can include will be four.

9
00:00:30,880 --> 00:00:39,700
Over here notice that there is no point going down this branch or even making this call because we don't

10
00:00:39,700 --> 00:00:41,320
have two more elements.

11
00:00:41,320 --> 00:00:43,090
We just have one more element.

12
00:00:43,090 --> 00:00:46,450
So the maximum that we can get over here is three comma four.

13
00:00:46,450 --> 00:00:49,990
And there's nothing more or there's nothing beyond four.

14
00:00:49,990 --> 00:00:54,130
So there is no need to create this or go down this branch.

15
00:00:54,130 --> 00:00:59,950
So in the initial approach we had said that J will take the values from I to N.

16
00:00:59,950 --> 00:01:09,100
But based on this observation over here, we actually don't need to go up to n now at any point.

17
00:01:09,340 --> 00:01:12,910
Let's say the car array has some length.

18
00:01:12,910 --> 00:01:21,790
So the number of items needed which have to be added to the car array would be k minus the current length

19
00:01:21,790 --> 00:01:23,590
of the current array.

20
00:01:23,590 --> 00:01:24,070
Right?

21
00:01:24,070 --> 00:01:29,290
For example, if the current array has one element and over here k is equal to three.

22
00:01:29,290 --> 00:01:34,690
So the needed number of elements would be three minus one which is equal to two.

23
00:01:34,720 --> 00:01:47,260
So j just has to go from I to x instead of I to n, where x over here is equal to n minus need, which

24
00:01:47,260 --> 00:01:50,050
is what we calculated over here minus one.

25
00:01:50,050 --> 00:01:51,100
Now why is that.

26
00:01:51,100 --> 00:01:53,470
So let's take an example to understand this.

27
00:01:54,800 --> 00:01:55,940
Over here.

28
00:01:55,940 --> 00:02:02,960
Notice that Cur is equal to just this array over here with one element.

29
00:02:03,440 --> 00:02:04,820
And again this is three.

30
00:02:04,820 --> 00:02:06,740
This is four and this is five.

31
00:02:06,740 --> 00:02:11,360
So over here cur is just this array which has one element.

32
00:02:11,360 --> 00:02:18,710
Because the size of cur is one need at this point will be three minus one which is equal to two.

33
00:02:18,710 --> 00:02:28,400
And if we were to calculate n which is four minus need minus one, that's four minus two minus one which

34
00:02:28,400 --> 00:02:30,680
is four minus one which is equal to three.

35
00:02:31,650 --> 00:02:40,170
What this optimization enables us to do is that we don't need to go from j is equal to two all the way

36
00:02:40,170 --> 00:02:41,010
up to four.

37
00:02:41,010 --> 00:02:43,350
We just need to go up to three.

38
00:02:43,350 --> 00:02:49,710
And again, this means that this call is unnecessary because we get one comma four, but then we don't

39
00:02:49,710 --> 00:02:54,600
have any more elements to build a combination of size three.

40
00:02:54,600 --> 00:03:01,590
So J just needs to go from I to x where x is equal to n minus need minus one.

41
00:03:01,590 --> 00:03:06,870
And that's why in this case it just has to go from two up to three.

42
00:03:06,900 --> 00:03:10,110
Now over here again let me just quickly demonstrate it.

43
00:03:10,110 --> 00:03:13,290
So the elements available are 123, four.

44
00:03:13,290 --> 00:03:20,430
And when we do n minus need that would be four minus two which is two.

45
00:03:20,430 --> 00:03:22,380
So we need two elements.

46
00:03:22,380 --> 00:03:29,490
But when we want to convert it to what value j can actually take we need to subtract one from this need

47
00:03:29,490 --> 00:03:32,460
over here so that four minus one gives us three.

48
00:03:32,460 --> 00:03:36,510
And that indicates that j can go up to the value three.

49
00:03:36,510 --> 00:03:40,170
So again in this case j just starts from two.

50
00:03:40,200 --> 00:03:42,990
So j can take the values from 2 to 3.

51
00:03:42,990 --> 00:03:46,050
And there is no need to go from 2 to 4.

52
00:03:46,050 --> 00:03:48,570
So this is an optimization that we can make.

53
00:03:48,570 --> 00:03:54,000
Now let's take a look at how we can incorporate it in the code that we have previously written.