Welcome back.
Let's now get into the code for solving combination sum two.
Okay.
So the notable differences between combination sum won and combination sum two is that there can be
duplicates in the input array okay.
So in the candidates array we could have duplicates.
So that's something that we need to take care of.
And it's also mentioned that we can use a candidate only one time.
All right.
So these are the important things that we need to keep in mind.
Now let's try to see what differences we have to do over here with respect to combination someone.
Now the first thing that you can see is we have to sort the candidates array.
And we have discussed this in the method video in detail why this is required.
So we are implementing this over here and we are sorting the candidates array.
Now before we get into the details of the code, let's first think about the skeleton of the solution
that we have written over here.
So this over here is a recursive solution.
And we are using a helper function which at this point we are just calling Backtrack okay.
And we are calling the helper function for the first time over here.
And we also have a results array which we have initialized over here.
And in the helper function, whenever we get a suitable combination, we push it to the result array.
We in fact make a copy of the current array and push it to the result array.
And over here notice we are returning the result array.
So this is the skeleton of the approach that we have over here.
And you will find that it's pretty similar to what we have written for combination someone.
Now the first thing that you can notice over here is we are going ahead and sorting the candidates array,
which is given to us now as to why we are doing this.
We have discussed this in detail in a previous video, so I'm not going to repeat it over here.
So after sorting the candidates array, what we do is we call the backtrack function.
And the initial inputs are we are starting at index zero.
And at this point the sum is equal to zero because Car does not have any element.
Now once we are inside the helper function which we have called backtrack, notice we have over here
the base case.
And over here we have the recursive case.
Now let's take a look at the base case.
Now, the first thing that you can notice over here is if we see that cur sum is equal to target, then
we have found a suitable combination of elements which add up to the target value.
And therefore we make a copy of cur and we push it to the results array.
And then we can just return.
So this is part of the base case.
And again remember we are making a copy of cur because this is a backtracking solution.
And we are making changes to Cur in place.
Now the other thing that we have over here is if cur sum is greater than target, then we can just return.
And the reason for that is all the elements in the candidates array are positive.
So we don't have negative numbers in the candidates array.
And therefore if at any point chasm is already greater than target, by adding more elements to the
Cur array, we will just be increasing cur some, right?
So that's why this no point in continuing down that branch, and we can just prune that branch by returning.
And there's one more interesting thing that we have over here.
Now, this is something that we did not have for combination sum one okay.
Now the difference is that in combination sum one, whenever we recursively call the helper function,
you would remember we would actually pass the start index as j instead of j plus one.
And the reason for that was in combination sum one.
It was allowed to use a candidate multiple times, but over here we are allowed to use a candidate only
one time.
And that's why in the recursive call we pass j plus one.
And because we do that, there could be a case where the start index that we pass to the helper function
is actually greater than the last valid index, which is candidates dot length minus one.
So if this happens then also we just return and we stop going down further that branch okay.
So this is the base case for the solution.
Now let's take a look at the recursive case.
Now you will see that we have made an important change in the recursive case.
And we have discussed this in the previous video and the change that we have made is in a particular
recursive call okay.
So whenever we are pushing to the current array we will not push the same value twice.
So if we see that a particular value let's say candidates at J, let's say candidates at one and candidates
at two have the same value, then when we encounter candidates at one, it's fine.
We would not have that particular element in the hash table, okay.
We would not have that particular key in the hash table.
And we go ahead and do all of these steps.
But when we come to candidates, two, if it has the same value as candidates one, then we would not
want to push that value to Cur.
And we have discussed the reason for that.
It's because we want to avoid duplicates.
And notice over here what we have done is if we see that candidates at J is already a key, which is
there in the hash map, then we just avoid that branch.
We prune that branch and go to the next value of J.
But on the other hand, if that particular key is not there in the hash table, then we proceed.
Okay.
So first of all we add it to the hash table or the object okay.
And then we go ahead and do the same steps that we had done for combination sum one with the difference
that over here we are passing j plus one instead of J.
And we have discussed the reason for that, which is that we can use a candidate only one time.
So over here notice we are doing curved or push candidates j.
Then we are recursively calling the helper function and we are passing j plus one, the new sum and
again the cur array.
And after that we have to do the backtracking step which is a dot pop.
So this is how we can solve this question.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's passing all the test cases.
Now do remember to make use of the user logs in case you get stuck and you want to debug your code.