1 00:00:00,440 --> 00:00:08,540 In the previous video, we have seen an example where n was equal to four and k was equal to two. 2 00:00:08,750 --> 00:00:16,460 So in that case, these were the six combinations that we could form using this. 3 00:00:16,460 --> 00:00:19,610 Let's make a few interesting observations. 4 00:00:19,640 --> 00:00:26,870 Notice over here that in these three combinations we have the starting value as one. 5 00:00:26,870 --> 00:00:31,070 And then the second value is changing from 2 to 4. 6 00:00:31,100 --> 00:00:38,480 This could be thought of as if we have two pointers where I is pointing at one. 7 00:00:38,480 --> 00:00:46,190 And then for this instance j is iterating from 2 to 4, or j is going from two up to four. 8 00:00:46,460 --> 00:00:48,980 So we get these three combinations. 9 00:00:49,780 --> 00:00:55,840 Now we move on I to two and J takes the values from 3 to 4. 10 00:00:55,840 --> 00:00:58,780 And again we get these two combinations. 11 00:00:58,780 --> 00:01:06,370 And finally I comes to three and j just takes the value four which gives us this combination over here. 12 00:01:06,580 --> 00:01:12,490 Let's see if we can use this to come up with the generic approach to solve this question. 13 00:01:12,880 --> 00:01:21,880 Now to think through about the approach that we can take, let's take an example where n is equal to 14 00:01:21,880 --> 00:01:24,340 four and k is equal to three. 15 00:01:24,370 --> 00:01:32,380 Now we start with an empty array and we start with the first pointer pointing to the value one. 16 00:01:32,410 --> 00:01:40,660 Now at this point let's allow the value of j to go from I to n. 17 00:01:43,640 --> 00:01:52,370 So when I is equal to one, we will append that value to the empty array and we get one when I is equal 18 00:01:52,370 --> 00:01:52,790 to two. 19 00:01:52,820 --> 00:01:54,860 We attempt two to the empty array. 20 00:01:54,860 --> 00:01:57,470 We get two, we get three, we get four. 21 00:01:57,470 --> 00:01:59,450 So we get these four branches. 22 00:01:59,480 --> 00:02:04,160 Now over here we recursively call the same function again. 23 00:02:04,160 --> 00:02:07,370 And we make I equal to two at this point. 24 00:02:07,550 --> 00:02:11,360 When we do that we get the value of j as two. 25 00:02:11,360 --> 00:02:17,150 So we add two to this array over here and it changes to one comma two. 26 00:02:17,240 --> 00:02:22,580 And in a similar manner when j takes the value three we get one comma three. 27 00:02:22,580 --> 00:02:28,940 When j takes the value four, we get one comma four, and we recursively call the function again, making 28 00:02:28,940 --> 00:02:30,140 I equal to three. 29 00:02:30,140 --> 00:02:35,450 So at this point, when j takes the value three, we get one, two, three. 30 00:02:36,020 --> 00:02:42,320 And over here, because the length of curve at this point is equal to k, we add this to the results 31 00:02:42,320 --> 00:02:44,420 array and we backtrack. 32 00:02:44,420 --> 00:02:48,560 We come back and we pop this three which is the backtracking step. 33 00:02:50,370 --> 00:02:55,470 And then we come to the next branch where we add four, so we get one, two, four. 34 00:02:55,470 --> 00:02:56,130 Again. 35 00:02:56,130 --> 00:02:58,350 This is also added to the results array. 36 00:02:58,350 --> 00:03:00,480 And it goes on in this manner. 37 00:03:00,480 --> 00:03:03,540 So this is how we can solve this problem. 38 00:03:03,540 --> 00:03:06,150 So notice over here what is it that we are doing. 39 00:03:06,150 --> 00:03:09,000 So we just have two pointers. 40 00:03:09,000 --> 00:03:11,430 And initially I is one. 41 00:03:11,430 --> 00:03:14,970 And J takes the values from I to n. 42 00:03:14,970 --> 00:03:18,090 And then we just keep adding the values to cur. 43 00:03:18,090 --> 00:03:19,890 So over here we added one. 44 00:03:19,890 --> 00:03:24,660 Then in the next call in the next recursive call j takes the value two. 45 00:03:24,690 --> 00:03:26,040 So we add that to the array. 46 00:03:26,040 --> 00:03:27,300 We get one comma two. 47 00:03:27,330 --> 00:03:33,060 Again in the recursive call, j takes the value three, and we add that to the current array. 48 00:03:33,060 --> 00:03:34,740 So it becomes one two, three. 49 00:03:34,740 --> 00:03:35,970 And then we pop. 50 00:03:35,970 --> 00:03:40,080 So it again changes to one comma two and we add four. 51 00:03:40,080 --> 00:03:42,120 So we get one comma two comma four. 52 00:03:42,120 --> 00:03:43,380 We pop the four. 53 00:03:43,380 --> 00:03:49,350 We get back to one comma two, we pop the two, we get back to one, and then we add three. 54 00:03:49,350 --> 00:03:51,240 So it becomes one comma three. 55 00:03:51,240 --> 00:03:53,940 And then in the next call we would add four. 56 00:03:53,940 --> 00:03:56,430 So we get one comma three comma four. 57 00:03:56,430 --> 00:03:57,780 And it goes on like this. 58 00:03:57,780 --> 00:04:03,750 So this is the backtracking recursive approach that we can take to solve this problem. 59 00:04:04,140 --> 00:04:10,620 In the beginning part of this video, when we were making an observation, we had seen that starting 60 00:04:10,620 --> 00:04:18,360 with one, the combinations when k was equal to two, where one comma two, one comma three and one 61 00:04:18,360 --> 00:04:19,410 comma four. 62 00:04:19,990 --> 00:04:22,000 Just for our learning. 63 00:04:22,000 --> 00:04:29,020 What part of the algorithm takes care of this that these values are greater than the starting value. 64 00:04:29,020 --> 00:04:31,900 So that's taken care of by the recursive call. 65 00:04:31,900 --> 00:04:38,590 Notice that initially when we had one and we recursively call the same function again we are incrementing 66 00:04:38,590 --> 00:04:39,580 the value of I. 67 00:04:39,580 --> 00:04:42,460 And over here notice we are starting at two. 68 00:04:42,460 --> 00:04:48,010 And this goes on up to n which takes care of what we observed in the beginning.