1
00:00:00,080 --> 00:00:03,710
Let's now get into the code for solving combination sum one.

2
00:00:03,740 --> 00:00:08,300
Okay, so let's first take a look at the skeleton of the code that we have over here.

3
00:00:08,300 --> 00:00:10,040
And then let's get into the details.

4
00:00:10,040 --> 00:00:17,420
So as the question asks we need to identify a set of numbers from the candidates array such that the

5
00:00:17,420 --> 00:00:19,640
values add up to the target value.

6
00:00:19,640 --> 00:00:26,090
And in the question it's also given that the candidates array has only non negative values.

7
00:00:27,630 --> 00:00:28,320
Okay.

8
00:00:28,320 --> 00:00:34,800
And it's also mentioned in the question that we can include a number from the candidates array multiple

9
00:00:34,800 --> 00:00:35,460
times.

10
00:00:35,460 --> 00:00:36,990
So this is given in the question.

11
00:00:36,990 --> 00:00:41,010
So over here we have followed a recursive approach for solving this question.

12
00:00:41,010 --> 00:00:42,780
So we have used the helper function.

13
00:00:42,780 --> 00:00:45,960
And we have called the helper function combination some recursive.

14
00:00:45,960 --> 00:00:49,230
And we are calling the helper function for the first time over here.

15
00:00:49,230 --> 00:00:52,290
And we also have declared an array rest over here.

16
00:00:52,290 --> 00:00:58,500
And at every point when we identify a combination of values from the candidates array such that the

17
00:00:58,500 --> 00:01:03,720
values add up to target, we make a copy of that particular combination, and we push it to the results

18
00:01:03,720 --> 00:01:04,350
array over here.

19
00:01:04,350 --> 00:01:06,600
And finally we return the results array.

20
00:01:06,600 --> 00:01:09,750
So this is the skeleton of the approach that we have over here.

21
00:01:09,750 --> 00:01:11,790
Now let's take a look at the details.

22
00:01:11,790 --> 00:01:18,030
So to the helper function notice that the things that are passed to it are the starting index okay.

23
00:01:18,030 --> 00:01:19,740
So that's what we have over here.

24
00:01:19,740 --> 00:01:24,720
And we have an array over here which we are passing to the helper function to track the current state.

25
00:01:24,720 --> 00:01:30,360
Because we need something to track what the combination of elements looks like at any point.

26
00:01:30,360 --> 00:01:32,310
So for that we have this array.

27
00:01:32,310 --> 00:01:38,610
And then we also have a value which indicates the current sum of the elements which have been added

28
00:01:38,610 --> 00:01:39,120
to cur.

29
00:01:39,120 --> 00:01:42,390
So these are the three things that we are passing to the helper function.

30
00:01:42,390 --> 00:01:47,370
And initially when we call the helper function, the values that we pass to it are zero.

31
00:01:47,370 --> 00:01:51,450
Because obviously we have to start at the first index of the candidates array.

32
00:01:51,450 --> 00:01:57,450
And at this point CR is just an empty array, and the sum of the values in the current array is zero

33
00:01:57,450 --> 00:01:59,040
because nothing has been added to it.

34
00:01:59,040 --> 00:01:59,430
All right.

35
00:01:59,460 --> 00:02:01,410
Now let's go a little bit deeper.

36
00:02:01,410 --> 00:02:05,100
So over here let's take a look at the helper function in detail.

37
00:02:05,100 --> 00:02:08,040
So first of all we have the base case over here.

38
00:02:08,520 --> 00:02:14,400
Notice that if cur sum at any point is greater than the target then we just return.

39
00:02:14,400 --> 00:02:20,310
This is so because it's given that the values in the candidates array are non-negative.

40
00:02:20,310 --> 00:02:27,360
So if at any point already the sum of the values added to cur is greater than target, then by adding

41
00:02:27,360 --> 00:02:33,840
more values to it which are non negative, we will just keep increasing the sum and we would not be

42
00:02:33,840 --> 00:02:37,890
able to decrease the sum because there are no negative values in the candidates array.

43
00:02:37,890 --> 00:02:41,760
So that's why if cur sum is greater than target, we can just return.

44
00:02:41,760 --> 00:02:48,540
And on the other hand, if at any point we see that cur sum is equal to target, then we have identified

45
00:02:48,540 --> 00:02:54,540
a set of values from the candidates array in a manner that the values add up to the target value, and

46
00:02:54,540 --> 00:02:59,130
therefore we make a copy of cur at this point and we push it to the results array.

47
00:02:59,160 --> 00:03:04,740
Now again we make a copy and push it, because at a later stage cur will keep changing because we are

48
00:03:04,740 --> 00:03:06,660
making changes to cur in place.

49
00:03:06,660 --> 00:03:11,280
We are not making new arrays at every point we are using the same cur array, and we are just trying

50
00:03:11,280 --> 00:03:16,920
to identify all the possible combinations of elements from the candidates array that add up to target.

51
00:03:16,920 --> 00:03:21,180
So that's why we make a copy of Cur over here and we push it to the results array.

52
00:03:21,180 --> 00:03:23,460
So this over here is the base case.

53
00:03:23,460 --> 00:03:25,470
Now what about the recursive case.

54
00:03:25,470 --> 00:03:29,310
So we have the recursive case over here.

55
00:03:29,310 --> 00:03:37,920
So if none of these is true then we have a variable j which takes the values from index up to the last

56
00:03:37,920 --> 00:03:40,440
valid index in the candidates array okay.

57
00:03:40,440 --> 00:03:43,560
And for each value of j we just push it to cur.

58
00:03:43,560 --> 00:03:46,590
And we call the helper function recursively.

59
00:03:46,590 --> 00:03:53,430
And notice in this recursive call we still pass the start index as j itself, because in the question

60
00:03:53,430 --> 00:03:56,760
it's mentioned that a value can be used multiple times.

61
00:03:57,500 --> 00:04:04,640
So that's why again we pass the index j itself, even though we have just now included the value at

62
00:04:04,640 --> 00:04:05,930
index J Tucker.

63
00:04:05,960 --> 00:04:06,290
Okay.

64
00:04:06,290 --> 00:04:08,360
So that's why we have J over here.

65
00:04:08,360 --> 00:04:13,670
And then we increment the sum because a new value has been added to Kur.

66
00:04:13,670 --> 00:04:16,100
And we also pass Kur to the helper function.

67
00:04:16,100 --> 00:04:21,440
And once we come out of this we do the backtracking step which is to pop the value that we just added

68
00:04:21,440 --> 00:04:22,400
to the Kur array.

69
00:04:22,400 --> 00:04:25,460
So this is how we can solve combination sum one.

70
00:04:25,460 --> 00:04:29,540
Now let's go ahead and run this code and see if it's passing all the test cases.

71
00:04:30,930 --> 00:04:33,450
And you can see that it's passing all the test cases.

72
00:04:33,450 --> 00:04:39,180
Again, do make use of the user logs in case you're stuck and you want some help to debug your code.