So what are the major differences between combination sum one and combination sum two?
Now in combination sum one, it was given that the input array would consist of distinct numbers, but
in combination sum two, we have seen that the input array can have duplicates.
In fact, we have seen an example where the input array had two times the number three occurring.
Another difference between these two questions is that in combination sum one, it's mentioned that
a candidate number can be used multiple times, but in combination sum two it's mentioned that a number
can be used only one time.
Now, because of these changes between these two questions, we have to slightly tweak the approach
to solve combination sum two.
Given these changes that we have discussed over here, and the fact that it's mentioned in the question
that the output set should not have duplicate combinations.
Let's see what would be the problems that we would encounter if we incorporated the same algorithm that
we used to solve combination sum one in this question.
So for this, let's take an example.
Let's say the target value given to us is eight.
And the candidates array is two, three, four, three and five.
Now, as per the approach that we have discussed for combination sum one we would have a curr array
which is initially empty.
And then we would go over these elements and add these elements to the array.
So the different branches in the recursive tree would be these over here.
So in this branch we have added the element two.
Over here we have added the element three.
And it goes on in this manner.
So this is what we have seen in the videos where we discussed combination sum one.
Now let's try to go down this branch over here.
So we have used this element.
So when we go down this branch now in combination sum one we would have again added this element.
And we would have three comma three.
But over here because it's mentioned that we can use one element only once, let's not do that.
But let's just rather go to the next element.
So the branches over here would be three comma four.
And three comma three because you have this three and this three and three comma five.
Now let's also go down this branch over here.
So we have added three which is this element.
Now again we are not going to add three comma three over here because we can use one element only once
as per this question.
So the branch that we will see when we go down over here would be three comma five because we will add
this five to it.
So we have three comma five over here.
Now notice that over here also you have three comma five which adds up to eight.
And over here also you have three comma five which adds up to eight.
So these are duplicates right.
And the question clearly mentions that we should not have duplicate combinations in the output set.
So this is something that we need to prevent over here.
And for preventing it.
What we need to do is at a particular instance when we are going from a particular start index to the
last index, we will add a value only once.
So for example, over here in this particular instance, when we are starting at index zero and going
up to the last index, when we see over here that we have already added three ones.
And then when we come over here, because we have encountered three previously, we will not add this
particular three over here and we will prune this branch over here.
Now you can do this in multiple ways.
Now over here I'll just use a simple dictionary for tracking this and pruning this branch.
So this is something that we will see when we write the code.
So we will in one particular instance when we go from a start index till the last index we will add
a particular value only once.
And if duplicates occur we will just skip over them.
Now there's one more interesting thing that we need to take care when we solve this question, let's
try to understand what is the need for sorting the input array or the candidates array, because this
is something that would be required for solving this question.
So for this again let's take another example.
Let's say the candidates array which is given to us is 4141.
And let's try to draw the recursion tree for this without sorting the input array.
So we will implement the HashMap.
So initially we have four over here this will get added in a branch.
And then we have one.
But then when we encounter the next four because we already had a four we will not have a branch over
here.
We'll prune that branch.
And similarly we will prune the branch that starts with one as well.
So in this case, because again we have discussed this previously, we will have only these two branches
when we go down this branch over here we have added this four.
So we start over here.
We are going to start at the next index, because it's mentioned in the question that a particular candidate
can be only used once.
So that's why we'll go to the next index.
And then we'll add this to this over here.
So we have four comma one.
And then we'll have four comma four.
And again when we encounter one again that branch will be pruned as we have just previously discussed.
Now if we go down this branch over here, we have added this one.
And we will be going to the next index which is four.
So we'll have one comma four and then we will have one comma one.
Now notice that over here you have one comma four.
And over here you have four comma one.
So again we are encountering duplicates.
And to avoid this it's very important that the input array has to be sorted.
Now what would be the case if we had sorted this before going down this path.
So if we had sorted it the input array would look like this.
We will have one, one, four, four.
And then the branches over here will be one comma four.
Because initially we'll have one, we'll have one added.
Then again because we are encountering a one that branch would be pruned.
Then we encounter four.
So we have a branch over here.
And when we encounter the next four that branch would be pruned.
So this is something that we have previously discussed.
Now when we go down over here we added this one.
And then we'll start at the next index.
So we'll have one comma one over here and one comma four.
We won't have one more one comma four because that branch would be pruned because we already had a four
over here.
And then in this branch we added this four.
And we'll go to the next index and we'll have four comma four over here.
So notice that by sorting the input array we have avoided this scenario where one comma 4 or 4 comma
one which were duplicates were occurring.
So over here one comma four is only occurring once.
So this is the approach that we will take to solve this question.
Or these are the slight tweaks that we need to do to the approach that you have discussed.
For combination.
Someone first of all, we will go to the next index when we call the helper function.
That's because a particular.
Candidate can only be used once.
Secondly, for every instance when we go from a particular start index to the last index, we will have
something to track whether a particular candidate occurred already.
And if we see that something that had previously occurred is coming again, we will skip over to the
next value.
Now we can do this, or we can implement this in code in multiple ways.
But over here I'm going to use a dictionary or a hash table to do this.
And finally we will also have to sort the input array which is given to us.
And we have seen that this also is required to avoid the occurrence of duplicate combinations in the
output set.