1
00:00:00,500 --> 00:00:07,100
So what are the major differences between combination sum one and combination sum two?

2
00:00:07,130 --> 00:00:15,650
Now in combination sum one, it was given that the input array would consist of distinct numbers, but

3
00:00:15,650 --> 00:00:20,660
in combination sum two, we have seen that the input array can have duplicates.

4
00:00:20,660 --> 00:00:26,210
In fact, we have seen an example where the input array had two times the number three occurring.

5
00:00:26,570 --> 00:00:33,020
Another difference between these two questions is that in combination sum one, it's mentioned that

6
00:00:33,020 --> 00:00:40,280
a candidate number can be used multiple times, but in combination sum two it's mentioned that a number

7
00:00:40,280 --> 00:00:42,350
can be used only one time.

8
00:00:42,350 --> 00:00:48,440
Now, because of these changes between these two questions, we have to slightly tweak the approach

9
00:00:48,440 --> 00:00:51,230
to solve combination sum two.

10
00:00:51,590 --> 00:00:57,590
Given these changes that we have discussed over here, and the fact that it's mentioned in the question

11
00:00:57,590 --> 00:01:01,700
that the output set should not have duplicate combinations.

12
00:01:01,730 --> 00:01:09,200
Let's see what would be the problems that we would encounter if we incorporated the same algorithm that

13
00:01:09,200 --> 00:01:12,680
we used to solve combination sum one in this question.

14
00:01:12,680 --> 00:01:15,440
So for this, let's take an example.

15
00:01:15,440 --> 00:01:19,190
Let's say the target value given to us is eight.

16
00:01:19,190 --> 00:01:24,080
And the candidates array is two, three, four, three and five.

17
00:01:24,110 --> 00:01:30,470
Now, as per the approach that we have discussed for combination sum one we would have a curr array

18
00:01:30,470 --> 00:01:32,060
which is initially empty.

19
00:01:32,060 --> 00:01:36,680
And then we would go over these elements and add these elements to the array.

20
00:01:36,680 --> 00:01:41,300
So the different branches in the recursive tree would be these over here.

21
00:01:41,300 --> 00:01:44,450
So in this branch we have added the element two.

22
00:01:44,450 --> 00:01:46,430
Over here we have added the element three.

23
00:01:46,430 --> 00:01:48,110
And it goes on in this manner.

24
00:01:48,110 --> 00:01:52,640
So this is what we have seen in the videos where we discussed combination sum one.

25
00:01:52,790 --> 00:01:56,450
Now let's try to go down this branch over here.

26
00:01:56,450 --> 00:01:58,460
So we have used this element.

27
00:01:58,460 --> 00:02:04,550
So when we go down this branch now in combination sum one we would have again added this element.

28
00:02:04,550 --> 00:02:06,260
And we would have three comma three.

29
00:02:06,260 --> 00:02:12,440
But over here because it's mentioned that we can use one element only once, let's not do that.

30
00:02:12,440 --> 00:02:15,350
But let's just rather go to the next element.

31
00:02:15,350 --> 00:02:19,100
So the branches over here would be three comma four.

32
00:02:20,000 --> 00:02:25,070
And three comma three because you have this three and this three and three comma five.

33
00:02:25,460 --> 00:02:29,210
Now let's also go down this branch over here.

34
00:02:29,210 --> 00:02:31,940
So we have added three which is this element.

35
00:02:31,940 --> 00:02:37,790
Now again we are not going to add three comma three over here because we can use one element only once

36
00:02:37,790 --> 00:02:39,050
as per this question.

37
00:02:39,050 --> 00:02:45,650
So the branch that we will see when we go down over here would be three comma five because we will add

38
00:02:45,650 --> 00:02:46,520
this five to it.

39
00:02:46,520 --> 00:02:48,410
So we have three comma five over here.

40
00:02:48,890 --> 00:02:54,350
Now notice that over here also you have three comma five which adds up to eight.

41
00:02:54,350 --> 00:02:58,130
And over here also you have three comma five which adds up to eight.

42
00:02:58,130 --> 00:03:00,230
So these are duplicates right.

43
00:03:00,230 --> 00:03:07,580
And the question clearly mentions that we should not have duplicate combinations in the output set.

44
00:03:07,580 --> 00:03:10,790
So this is something that we need to prevent over here.

45
00:03:10,790 --> 00:03:12,650
And for preventing it.

46
00:03:12,650 --> 00:03:20,090
What we need to do is at a particular instance when we are going from a particular start index to the

47
00:03:20,090 --> 00:03:23,210
last index, we will add a value only once.

48
00:03:23,210 --> 00:03:30,350
So for example, over here in this particular instance, when we are starting at index zero and going

49
00:03:30,350 --> 00:03:34,850
up to the last index, when we see over here that we have already added three ones.

50
00:03:34,850 --> 00:03:41,000
And then when we come over here, because we have encountered three previously, we will not add this

51
00:03:41,000 --> 00:03:44,180
particular three over here and we will prune this branch over here.

52
00:03:44,180 --> 00:03:46,220
Now you can do this in multiple ways.

53
00:03:46,220 --> 00:03:52,490
Now over here I'll just use a simple dictionary for tracking this and pruning this branch.

54
00:03:52,490 --> 00:03:55,940
So this is something that we will see when we write the code.

55
00:03:55,940 --> 00:04:02,510
So we will in one particular instance when we go from a start index till the last index we will add

56
00:04:02,510 --> 00:04:04,550
a particular value only once.

57
00:04:04,550 --> 00:04:08,180
And if duplicates occur we will just skip over them.

58
00:04:08,270 --> 00:04:14,690
Now there's one more interesting thing that we need to take care when we solve this question, let's

59
00:04:14,690 --> 00:04:20,900
try to understand what is the need for sorting the input array or the candidates array, because this

60
00:04:20,900 --> 00:04:23,780
is something that would be required for solving this question.

61
00:04:23,780 --> 00:04:26,600
So for this again let's take another example.

62
00:04:26,600 --> 00:04:31,850
Let's say the candidates array which is given to us is 4141.

63
00:04:31,850 --> 00:04:36,950
And let's try to draw the recursion tree for this without sorting the input array.

64
00:04:36,950 --> 00:04:39,410
So we will implement the HashMap.

65
00:04:39,410 --> 00:04:43,370
So initially we have four over here this will get added in a branch.

66
00:04:43,370 --> 00:04:44,420
And then we have one.

67
00:04:44,420 --> 00:04:50,450
But then when we encounter the next four because we already had a four we will not have a branch over

68
00:04:50,450 --> 00:04:50,660
here.

69
00:04:50,660 --> 00:04:51,860
We'll prune that branch.

70
00:04:51,860 --> 00:04:55,490
And similarly we will prune the branch that starts with one as well.

71
00:04:55,490 --> 00:05:00,710
So in this case, because again we have discussed this previously, we will have only these two branches

72
00:05:00,710 --> 00:05:04,370
when we go down this branch over here we have added this four.

73
00:05:04,370 --> 00:05:05,810
So we start over here.

74
00:05:05,810 --> 00:05:10,580
We are going to start at the next index, because it's mentioned in the question that a particular candidate

75
00:05:10,580 --> 00:05:12,350
can be only used once.

76
00:05:12,350 --> 00:05:14,330
So that's why we'll go to the next index.

77
00:05:14,330 --> 00:05:17,270
And then we'll add this to this over here.

78
00:05:17,270 --> 00:05:19,070
So we have four comma one.

79
00:05:19,220 --> 00:05:22,160
And then we'll have four comma four.

80
00:05:22,160 --> 00:05:28,520
And again when we encounter one again that branch will be pruned as we have just previously discussed.

81
00:05:28,520 --> 00:05:32,690
Now if we go down this branch over here, we have added this one.

82
00:05:32,690 --> 00:05:35,630
And we will be going to the next index which is four.

83
00:05:35,630 --> 00:05:40,730
So we'll have one comma four and then we will have one comma one.

84
00:05:40,730 --> 00:05:44,510
Now notice that over here you have one comma four.

85
00:05:44,510 --> 00:05:46,700
And over here you have four comma one.

86
00:05:46,700 --> 00:05:49,310
So again we are encountering duplicates.

87
00:05:49,310 --> 00:05:55,400
And to avoid this it's very important that the input array has to be sorted.

88
00:05:55,400 --> 00:06:00,320
Now what would be the case if we had sorted this before going down this path.

89
00:06:00,320 --> 00:06:04,100
So if we had sorted it the input array would look like this.

90
00:06:04,130 --> 00:06:06,560
We will have one, one, four, four.

91
00:06:06,560 --> 00:06:10,130
And then the branches over here will be one comma four.

92
00:06:10,130 --> 00:06:12,680
Because initially we'll have one, we'll have one added.

93
00:06:12,680 --> 00:06:16,400
Then again because we are encountering a one that branch would be pruned.

94
00:06:16,400 --> 00:06:17,960
Then we encounter four.

95
00:06:17,960 --> 00:06:19,280
So we have a branch over here.

96
00:06:19,280 --> 00:06:23,390
And when we encounter the next four that branch would be pruned.

97
00:06:23,390 --> 00:06:25,640
So this is something that we have previously discussed.

98
00:06:25,640 --> 00:06:29,090
Now when we go down over here we added this one.

99
00:06:29,090 --> 00:06:31,250
And then we'll start at the next index.

100
00:06:31,250 --> 00:06:35,120
So we'll have one comma one over here and one comma four.

101
00:06:35,120 --> 00:06:40,040
We won't have one more one comma four because that branch would be pruned because we already had a four

102
00:06:40,040 --> 00:06:40,640
over here.

103
00:06:40,640 --> 00:06:43,850
And then in this branch we added this four.

104
00:06:43,850 --> 00:06:47,720
And we'll go to the next index and we'll have four comma four over here.

105
00:06:47,720 --> 00:06:55,760
So notice that by sorting the input array we have avoided this scenario where one comma 4 or 4 comma

106
00:06:55,760 --> 00:06:57,740
one which were duplicates were occurring.

107
00:06:57,740 --> 00:07:01,100
So over here one comma four is only occurring once.

108
00:07:01,100 --> 00:07:04,970
So this is the approach that we will take to solve this question.

109
00:07:04,970 --> 00:07:10,250
Or these are the slight tweaks that we need to do to the approach that you have discussed.

110
00:07:10,250 --> 00:07:11,030
For combination.

111
00:07:11,030 --> 00:07:17,330
Someone first of all, we will go to the next index when we call the helper function.

112
00:07:17,330 --> 00:07:19,040
That's because a particular.

113
00:07:19,180 --> 00:07:21,400
Candidate can only be used once.

114
00:07:21,430 --> 00:07:30,310
Secondly, for every instance when we go from a particular start index to the last index, we will have

115
00:07:30,310 --> 00:07:34,600
something to track whether a particular candidate occurred already.

116
00:07:34,600 --> 00:07:40,210
And if we see that something that had previously occurred is coming again, we will skip over to the

117
00:07:40,210 --> 00:07:41,080
next value.

118
00:07:41,110 --> 00:07:45,220
Now we can do this, or we can implement this in code in multiple ways.

119
00:07:45,220 --> 00:07:49,240
But over here I'm going to use a dictionary or a hash table to do this.

120
00:07:49,240 --> 00:07:54,460
And finally we will also have to sort the input array which is given to us.

121
00:07:54,460 --> 00:08:00,820
And we have seen that this also is required to avoid the occurrence of duplicate combinations in the

122
00:08:00,820 --> 00:08:01,720
output set.