1
00:00:00,260 --> 00:00:01,160
Welcome back.

2
00:00:01,160 --> 00:00:05,180
Let's now get into the code for solving combination sum two.

3
00:00:05,210 --> 00:00:05,600
Okay.

4
00:00:05,600 --> 00:00:12,170
So the notable differences between combination sum won and combination sum two is that there can be

5
00:00:12,170 --> 00:00:14,420
duplicates in the input array okay.

6
00:00:14,420 --> 00:00:17,780
So in the candidates array we could have duplicates.

7
00:00:17,780 --> 00:00:20,030
So that's something that we need to take care of.

8
00:00:20,030 --> 00:00:24,410
And it's also mentioned that we can use a candidate only one time.

9
00:00:28,010 --> 00:00:28,520
All right.

10
00:00:28,520 --> 00:00:31,460
So these are the important things that we need to keep in mind.

11
00:00:31,490 --> 00:00:37,160
Now let's try to see what differences we have to do over here with respect to combination someone.

12
00:00:37,190 --> 00:00:41,090
Now the first thing that you can see is we have to sort the candidates array.

13
00:00:41,090 --> 00:00:45,230
And we have discussed this in the method video in detail why this is required.

14
00:00:45,230 --> 00:00:48,830
So we are implementing this over here and we are sorting the candidates array.

15
00:00:48,860 --> 00:00:54,230
Now before we get into the details of the code, let's first think about the skeleton of the solution

16
00:00:54,230 --> 00:00:55,190
that we have written over here.

17
00:00:55,190 --> 00:00:58,070
So this over here is a recursive solution.

18
00:00:58,070 --> 00:01:02,420
And we are using a helper function which at this point we are just calling Backtrack okay.

19
00:01:02,420 --> 00:01:05,780
And we are calling the helper function for the first time over here.

20
00:01:05,780 --> 00:01:10,040
And we also have a results array which we have initialized over here.

21
00:01:10,040 --> 00:01:16,460
And in the helper function, whenever we get a suitable combination, we push it to the result array.

22
00:01:16,460 --> 00:01:20,960
We in fact make a copy of the current array and push it to the result array.

23
00:01:20,960 --> 00:01:23,900
And over here notice we are returning the result array.

24
00:01:23,900 --> 00:01:27,200
So this is the skeleton of the approach that we have over here.

25
00:01:27,200 --> 00:01:31,190
And you will find that it's pretty similar to what we have written for combination someone.

26
00:01:31,190 --> 00:01:36,590
Now the first thing that you can notice over here is we are going ahead and sorting the candidates array,

27
00:01:36,590 --> 00:01:39,230
which is given to us now as to why we are doing this.

28
00:01:39,260 --> 00:01:44,060
We have discussed this in detail in a previous video, so I'm not going to repeat it over here.

29
00:01:44,060 --> 00:01:49,010
So after sorting the candidates array, what we do is we call the backtrack function.

30
00:01:49,010 --> 00:01:52,520
And the initial inputs are we are starting at index zero.

31
00:01:52,520 --> 00:01:57,860
And at this point the sum is equal to zero because Car does not have any element.

32
00:01:57,860 --> 00:02:03,620
Now once we are inside the helper function which we have called backtrack, notice we have over here

33
00:02:03,620 --> 00:02:04,820
the base case.

34
00:02:04,820 --> 00:02:08,090
And over here we have the recursive case.

35
00:02:09,380 --> 00:02:11,420
Now let's take a look at the base case.

36
00:02:11,450 --> 00:02:17,570
Now, the first thing that you can notice over here is if we see that cur sum is equal to target, then

37
00:02:17,570 --> 00:02:22,280
we have found a suitable combination of elements which add up to the target value.

38
00:02:22,280 --> 00:02:27,770
And therefore we make a copy of cur and we push it to the results array.

39
00:02:27,770 --> 00:02:29,210
And then we can just return.

40
00:02:29,210 --> 00:02:30,950
So this is part of the base case.

41
00:02:30,950 --> 00:02:35,150
And again remember we are making a copy of cur because this is a backtracking solution.

42
00:02:35,150 --> 00:02:37,760
And we are making changes to Cur in place.

43
00:02:37,760 --> 00:02:43,850
Now the other thing that we have over here is if cur sum is greater than target, then we can just return.

44
00:02:43,850 --> 00:02:48,500
And the reason for that is all the elements in the candidates array are positive.

45
00:02:48,500 --> 00:02:51,680
So we don't have negative numbers in the candidates array.

46
00:02:51,680 --> 00:02:57,950
And therefore if at any point chasm is already greater than target, by adding more elements to the

47
00:02:57,950 --> 00:03:00,980
Cur array, we will just be increasing cur some, right?

48
00:03:00,980 --> 00:03:06,560
So that's why this no point in continuing down that branch, and we can just prune that branch by returning.

49
00:03:06,560 --> 00:03:09,260
And there's one more interesting thing that we have over here.

50
00:03:09,260 --> 00:03:13,580
Now, this is something that we did not have for combination sum one okay.

51
00:03:13,580 --> 00:03:19,460
Now the difference is that in combination sum one, whenever we recursively call the helper function,

52
00:03:19,460 --> 00:03:25,430
you would remember we would actually pass the start index as j instead of j plus one.

53
00:03:25,430 --> 00:03:28,280
And the reason for that was in combination sum one.

54
00:03:28,280 --> 00:03:34,490
It was allowed to use a candidate multiple times, but over here we are allowed to use a candidate only

55
00:03:34,490 --> 00:03:35,300
one time.

56
00:03:35,300 --> 00:03:39,050
And that's why in the recursive call we pass j plus one.

57
00:03:39,050 --> 00:03:45,830
And because we do that, there could be a case where the start index that we pass to the helper function

58
00:03:45,830 --> 00:03:51,320
is actually greater than the last valid index, which is candidates dot length minus one.

59
00:03:51,320 --> 00:03:57,320
So if this happens then also we just return and we stop going down further that branch okay.

60
00:03:57,320 --> 00:04:00,050
So this is the base case for the solution.

61
00:04:00,050 --> 00:04:02,150
Now let's take a look at the recursive case.

62
00:04:02,150 --> 00:04:05,930
Now you will see that we have made an important change in the recursive case.

63
00:04:05,930 --> 00:04:11,480
And we have discussed this in the previous video and the change that we have made is in a particular

64
00:04:11,480 --> 00:04:12,830
recursive call okay.

65
00:04:12,830 --> 00:04:19,040
So whenever we are pushing to the current array we will not push the same value twice.

66
00:04:19,040 --> 00:04:25,400
So if we see that a particular value let's say candidates at J, let's say candidates at one and candidates

67
00:04:25,400 --> 00:04:30,440
at two have the same value, then when we encounter candidates at one, it's fine.

68
00:04:30,440 --> 00:04:34,430
We would not have that particular element in the hash table, okay.

69
00:04:34,430 --> 00:04:37,130
We would not have that particular key in the hash table.

70
00:04:37,130 --> 00:04:39,650
And we go ahead and do all of these steps.

71
00:04:39,650 --> 00:04:45,800
But when we come to candidates, two, if it has the same value as candidates one, then we would not

72
00:04:45,800 --> 00:04:47,870
want to push that value to Cur.

73
00:04:47,870 --> 00:04:49,460
And we have discussed the reason for that.

74
00:04:49,460 --> 00:04:51,440
It's because we want to avoid duplicates.

75
00:04:51,440 --> 00:04:57,080
And notice over here what we have done is if we see that candidates at J is already a key, which is

76
00:04:57,080 --> 00:05:00,320
there in the hash map, then we just avoid that branch.

77
00:05:00,320 --> 00:05:03,350
We prune that branch and go to the next value of J.

78
00:05:03,350 --> 00:05:08,180
But on the other hand, if that particular key is not there in the hash table, then we proceed.

79
00:05:08,180 --> 00:05:08,510
Okay.

80
00:05:08,510 --> 00:05:12,110
So first of all we add it to the hash table or the object okay.

81
00:05:12,110 --> 00:05:17,780
And then we go ahead and do the same steps that we had done for combination sum one with the difference

82
00:05:17,780 --> 00:05:20,750
that over here we are passing j plus one instead of J.

83
00:05:20,750 --> 00:05:25,190
And we have discussed the reason for that, which is that we can use a candidate only one time.

84
00:05:25,190 --> 00:05:28,640
So over here notice we are doing curved or push candidates j.

85
00:05:28,640 --> 00:05:35,060
Then we are recursively calling the helper function and we are passing j plus one, the new sum and

86
00:05:35,060 --> 00:05:36,260
again the cur array.

87
00:05:36,380 --> 00:05:40,670
And after that we have to do the backtracking step which is a dot pop.

88
00:05:40,670 --> 00:05:43,190
So this is how we can solve this question.

89
00:05:43,190 --> 00:05:47,390
Now let's go ahead and run this code and see if it's passing all the test cases.

90
00:05:50,300 --> 00:05:53,060
And you can see that it's passing all the test cases.

91
00:05:53,090 --> 00:05:58,610
Now do remember to make use of the user logs in case you get stuck and you want to debug your code.