1
00:00:00,080 --> 00:00:01,730
Hey there and welcome back.

2
00:00:01,760 --> 00:00:06,320
Let's now discuss the method or the approach for solving this question.

3
00:00:06,350 --> 00:00:11,000
Now to discuss the approach that we can take, let's take an example.

4
00:00:11,000 --> 00:00:15,020
Let's say the array which is given to us is 2347.

5
00:00:15,020 --> 00:00:16,970
So this is the candidates array.

6
00:00:16,970 --> 00:00:20,180
And the target value which is given to us is seven.

7
00:00:20,180 --> 00:00:22,070
Now let me write the indices over here.

8
00:00:22,070 --> 00:00:24,980
So I have zero one, two and three.

9
00:00:25,070 --> 00:00:28,640
Now we are going to have a recursive function.

10
00:00:28,640 --> 00:00:33,290
And initially we are going to pass the start index as zero.

11
00:00:33,290 --> 00:00:39,170
Now for start index let me just denote it with I to be able to easily write it over here.

12
00:00:39,170 --> 00:00:42,170
So initially I is going to take the value zero.

13
00:00:42,170 --> 00:00:48,680
And then because we have seen in the example given to us that we will have to return an array of arrays

14
00:00:48,680 --> 00:00:55,010
where each of these elements over here should be a combination of numbers in the candidates array,

15
00:00:55,010 --> 00:00:55,970
which is given to us.

16
00:00:55,970 --> 00:00:57,830
That adds up to the target value.

17
00:00:57,830 --> 00:01:01,910
So we will need an array to store each of these combinations.

18
00:01:01,910 --> 00:01:03,680
So let's just call that car.

19
00:01:04,410 --> 00:01:10,290
And then finally this array over here will be the results array which is going to be returned.

20
00:01:10,320 --> 00:01:15,660
So to start with we know that the start index or I is equal to zero.

21
00:01:15,660 --> 00:01:18,960
And the current array is going to be an empty array.

22
00:01:18,960 --> 00:01:24,900
And the current sum is equal to zero because nothing has been added to the current array over here.

23
00:01:24,930 --> 00:01:25,500
Okay.

24
00:01:25,500 --> 00:01:29,880
So now this over here is going to be a recursive call to a function.

25
00:01:29,880 --> 00:01:37,620
And inside the body of this function we are going to have another pointer that will go from the value

26
00:01:37,620 --> 00:01:44,370
of the start index which is zero at this point till the last index in the candidates array.

27
00:01:44,370 --> 00:01:50,190
So in this case, because start index is equal to zero, it's going to go from zero up to three.

28
00:01:50,190 --> 00:01:55,260
And then each value at index j is going to be added to the current array over here.

29
00:01:55,260 --> 00:01:58,830
So again let me just draw the recursive tree over here.

30
00:01:58,830 --> 00:02:01,380
And that will make it very easy to understand.

31
00:02:01,380 --> 00:02:04,950
So when j is equal to zero the value is going to equal to.

32
00:02:04,980 --> 00:02:09,720
So when we add two to an empty array we'll just get an array with the value two.

33
00:02:09,750 --> 00:02:14,730
Similarly, when j is equal to one, the value is three, and when three is added to an empty array,

34
00:02:14,730 --> 00:02:15,840
we'll have three over here.

35
00:02:15,840 --> 00:02:18,510
And in a similar manner over here we have four.

36
00:02:18,510 --> 00:02:20,610
And over here we have seven.

37
00:02:20,640 --> 00:02:25,620
Now let's just draw out the recursion tree a bit more deeper.

38
00:02:25,620 --> 00:02:31,710
And we are not going to draw the complete tree, but let's just draw it to a level which is sufficient

39
00:02:31,710 --> 00:02:34,440
for us to understand the approach that we are discussing over here.

40
00:02:34,440 --> 00:02:40,890
So how would this branch over here go down further in the question, it's mentioned that an element

41
00:02:40,890 --> 00:02:44,460
can be taken multiple or an unlimited number of times.

42
00:02:44,460 --> 00:02:46,470
So over here two is already added.

43
00:02:46,470 --> 00:02:49,470
But we can again add two okay.

44
00:02:49,470 --> 00:02:56,850
So the next level for this branch over here will be two comma two two comma three two comma four and

45
00:02:56,850 --> 00:02:57,720
two comma seven.

46
00:02:57,720 --> 00:03:04,290
So this would be the next level in this branch over here we can make an interesting observation.

47
00:03:04,290 --> 00:03:09,570
Notice that this branch over here already has the values two and seven.

48
00:03:09,570 --> 00:03:13,380
And when you add this up you get nine which is greater than seven.

49
00:03:13,380 --> 00:03:19,680
So there is no point going down this branch further down because the value will only be greater than

50
00:03:19,680 --> 00:03:20,100
nine.

51
00:03:20,100 --> 00:03:22,770
But the target value itself is just seven.

52
00:03:22,770 --> 00:03:25,230
So we can prune this branch over here.

53
00:03:25,850 --> 00:03:32,270
So at any point, if the sum of the elements in coeur is going to be greater than the target value,

54
00:03:32,270 --> 00:03:38,420
that branch will be pruned, and the next level over here would again be two comma two.

55
00:03:38,420 --> 00:03:41,780
And then we add two, we add three, four and seven.

56
00:03:41,780 --> 00:03:43,190
So it would look like this.

57
00:03:44,820 --> 00:03:50,370
And the reason for this is that we can include two an unlimited number of times.

58
00:03:50,370 --> 00:03:57,690
And these branches are going to be pruned because the sum of the values incur at these instances is

59
00:03:57,690 --> 00:03:58,860
greater than seven.

60
00:03:58,890 --> 00:04:06,600
Also notice over here, if you add two and two and three, you get the value seven which is the target

61
00:04:06,600 --> 00:04:07,050
value.

62
00:04:07,050 --> 00:04:14,100
Therefore, we can add this value of cur to the results array which will be finally returned.

63
00:04:14,100 --> 00:04:20,730
And we don't need to go further down because we already found the combination of numbers that add up

64
00:04:20,730 --> 00:04:21,390
to target.

65
00:04:21,390 --> 00:04:26,250
Also notice if you were to go further down, you would get a value greater than target, right?

66
00:04:26,250 --> 00:04:29,100
So there is no point going down further over here as well.

67
00:04:29,100 --> 00:04:34,620
And then in this case again we would go down and we will add two to it three, four and seven.

68
00:04:34,620 --> 00:04:40,560
And any instance where the sum of the elements incur is greater than target would be pruned.

69
00:04:40,560 --> 00:04:47,430
And if we do get an instance where the sum of the values incur is equal to target, that would be added

70
00:04:47,430 --> 00:04:50,670
to the results array, which is what we did over here as well.

71
00:04:50,670 --> 00:04:56,970
Now again, we have just drawn out the recursion tree to some extent over here to get an idea of what's

72
00:04:56,970 --> 00:04:57,930
happening over here.

73
00:04:57,930 --> 00:05:02,190
Now there's one more interesting thing that you should notice or remember.

74
00:05:02,190 --> 00:05:06,780
And for this, let's draw the next level for this branch over here.

75
00:05:06,780 --> 00:05:12,180
So this is the instance where three is there in the current array and there's no other value.

76
00:05:12,180 --> 00:05:17,670
So in the next level we will not be adding values from two onwards.

77
00:05:17,670 --> 00:05:20,820
But rather we will only start from this index over here.

78
00:05:20,820 --> 00:05:23,940
So three was the element at index one.

79
00:05:23,940 --> 00:05:30,180
So in the next level for this branch we will start adding values only starting at index one.

80
00:05:30,180 --> 00:05:36,300
So the next level for this would be three comma three, three comma four and three comma seven.

81
00:05:36,300 --> 00:05:44,100
Now the reason for this is that if we had three comma two, notice that this is a repetition of this.

82
00:05:44,100 --> 00:05:49,860
And because we don't want duplicates in this manner, that's why we will not have such a branch over

83
00:05:49,860 --> 00:05:50,250
here.

84
00:05:50,250 --> 00:05:55,260
But rather we will start at the index which is the value added over here.

85
00:05:55,260 --> 00:05:59,790
So this would be three comma three, three comma four and three comma seven.

86
00:06:00,360 --> 00:06:05,820
So the next level after this would be three comma three comma three.

87
00:06:06,270 --> 00:06:10,290
And then you have three comma three comma four.

88
00:06:10,650 --> 00:06:14,700
And you have three comma three comma seven.

89
00:06:14,700 --> 00:06:18,240
And again it's another thing that these will be pruned.

90
00:06:18,240 --> 00:06:24,900
Because the sum of the elements incur at each of these instances is greater than the target value,

91
00:06:24,900 --> 00:06:26,520
which is equal to seven.

92
00:06:26,520 --> 00:06:32,940
Also notice that when you have three comma four over here, this adds up to seven, which is the target

93
00:06:32,940 --> 00:06:33,450
value.

94
00:06:33,450 --> 00:06:34,860
And therefore this.

95
00:06:34,860 --> 00:06:38,580
Over here, this instance of car will be added to the results array.

96
00:06:38,580 --> 00:06:41,580
Or a copy of this would be added to the results array.

97
00:06:42,180 --> 00:06:48,600
So this is how we can get all the combinations of elements in the candidates array, where an element

98
00:06:48,600 --> 00:06:55,830
can be taken an unlimited number of times, such that the values in the combination adds up to the target

99
00:06:55,830 --> 00:06:57,120
value which is given to us.

100
00:06:57,120 --> 00:07:02,970
And notice that this is a backtracking approach because the changes to occur are made in place.

101
00:07:02,970 --> 00:07:06,720
So for example, over here we see that this can be pruned.

102
00:07:06,720 --> 00:07:08,910
And then we would remove this seven.

103
00:07:08,910 --> 00:07:12,210
So we come back to this and then we would remove this two.

104
00:07:12,240 --> 00:07:15,600
So the current array again would be an empty array.

105
00:07:15,600 --> 00:07:17,490
And then we will add three to it.

106
00:07:17,490 --> 00:07:21,330
So again notice this is a typical backtracking approach.