Let's now discuss an optimization that we can make to the approach that we previously discussed over
here.
For example, notice that k is equal to three.
So every combination has to have a length of three.
But in this branch over here where we are starting with the value three.
And then the next value that we can include will be four.
Right.
So the next value that we can include will be four.
Over here notice that there is no point going down this branch or even making this call because we don't
have two more elements.
We just have one more element.
So the maximum that we can get over here is three comma four.
And there's nothing more or there's nothing beyond four.
So there is no need to create this or go down this branch.
So in the initial approach we had said that J will take the values from I to N.
But based on this observation over here, we actually don't need to go up to n now at any point.
Let's say the car array has some length.
So the number of items needed which have to be added to the car array would be k minus the current length
of the current array.
Right?
For example, if the current array has one element and over here k is equal to three.
So the needed number of elements would be three minus one which is equal to two.
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
is what we calculated over here minus one.
Now why is that.
So let's take an example to understand this.
Over here.
Notice that Cur is equal to just this array over here with one element.
And again this is three.
This is four and this is five.
So over here cur is just this array which has one element.
Because the size of cur is one need at this point will be three minus one which is equal to two.
And if we were to calculate n which is four minus need minus one, that's four minus two minus one which
is four minus one which is equal to three.
What this optimization enables us to do is that we don't need to go from j is equal to two all the way
up to four.
We just need to go up to three.
And again, this means that this call is unnecessary because we get one comma four, but then we don't
have any more elements to build a combination of size three.
So J just needs to go from I to x where x is equal to n minus need minus one.
And that's why in this case it just has to go from two up to three.
Now over here again let me just quickly demonstrate it.
So the elements available are 123, four.
And when we do n minus need that would be four minus two which is two.
So we need two elements.
But when we want to convert it to what value j can actually take we need to subtract one from this need
over here so that four minus one gives us three.
And that indicates that j can go up to the value three.
So again in this case j just starts from two.
So j can take the values from 2 to 3.
And there is no need to go from 2 to 4.
So this is an optimization that we can make.
Now let's take a look at how we can incorporate it in the code that we have previously written.