In the previous video, we have seen an example where n was equal to four and k was equal to two.
So in that case, these were the six combinations that we could form using this.
Let's make a few interesting observations.
Notice over here that in these three combinations we have the starting value as one.
And then the second value is changing from 2 to 4.
This could be thought of as if we have two pointers where I is pointing at one.
And then for this instance j is iterating from 2 to 4, or j is going from two up to four.
So we get these three combinations.
Now we move on I to two and J takes the values from 3 to 4.
And again we get these two combinations.
And finally I comes to three and j just takes the value four which gives us this combination over here.
Let's see if we can use this to come up with the generic approach to solve this question.
Now to think through about the approach that we can take, let's take an example where n is equal to
four and k is equal to three.
Now we start with an empty array and we start with the first pointer pointing to the value one.
Now at this point let's allow the value of j to go from I to n.
So when I is equal to one, we will append that value to the empty array and we get one when I is equal
to two.
We attempt two to the empty array.
We get two, we get three, we get four.
So we get these four branches.
Now over here we recursively call the same function again.
And we make I equal to two at this point.
When we do that we get the value of j as two.
So we add two to this array over here and it changes to one comma two.
And in a similar manner when j takes the value three we get one comma three.
When j takes the value four, we get one comma four, and we recursively call the function again, making
I equal to three.
So at this point, when j takes the value three, we get one, two, three.
And over here, because the length of curve at this point is equal to k, we add this to the results
array and we backtrack.
We come back and we pop this three which is the backtracking step.
And then we come to the next branch where we add four, so we get one, two, four.
Again.
This is also added to the results array.
And it goes on in this manner.
So this is how we can solve this problem.
So notice over here what is it that we are doing.
So we just have two pointers.
And initially I is one.
And J takes the values from I to n.
And then we just keep adding the values to cur.
So over here we added one.
Then in the next call in the next recursive call j takes the value two.
So we add that to the array.
We get one comma two.
Again in the recursive call, j takes the value three, and we add that to the current array.
So it becomes one two, three.
And then we pop.
So it again changes to one comma two and we add four.
So we get one comma two comma four.
We pop the four.
We get back to one comma two, we pop the two, we get back to one, and then we add three.
So it becomes one comma three.
And then in the next call we would add four.
So we get one comma three comma four.
And it goes on like this.
So this is the backtracking recursive approach that we can take to solve this problem.
In the beginning part of this video, when we were making an observation, we had seen that starting
with one, the combinations when k was equal to two, where one comma two, one comma three and one
comma four.
Just for our learning.
What part of the algorithm takes care of this that these values are greater than the starting value.
So that's taken care of by the recursive call.
Notice that initially when we had one and we recursively call the same function again we are incrementing
the value of I.
And over here notice we are starting at two.
And this goes on up to n which takes care of what we observed in the beginning.