Hey there and welcome back.
Let's now discuss the method or the approach for solving this question.
Now to discuss the approach that we can take, let's take an example.
Let's say the array which is given to us is 2347.
So this is the candidates array.
And the target value which is given to us is seven.
Now let me write the indices over here.
So I have zero one, two and three.
Now we are going to have a recursive function.
And initially we are going to pass the start index as zero.
Now for start index let me just denote it with I to be able to easily write it over here.
So initially I is going to take the value zero.
And then because we have seen in the example given to us that we will have to return an array of arrays
where each of these elements over here should be a combination of numbers in the candidates array,
which is given to us.
That adds up to the target value.
So we will need an array to store each of these combinations.
So let's just call that car.
And then finally this array over here will be the results array which is going to be returned.
So to start with we know that the start index or I is equal to zero.
And the current array is going to be an empty array.
And the current sum is equal to zero because nothing has been added to the current array over here.
Okay.
So now this over here is going to be a recursive call to a function.
And inside the body of this function we are going to have another pointer that will go from the value
of the start index which is zero at this point till the last index in the candidates array.
So in this case, because start index is equal to zero, it's going to go from zero up to three.
And then each value at index j is going to be added to the current array over here.
So again let me just draw the recursive tree over here.
And that will make it very easy to understand.
So when j is equal to zero the value is going to equal to.
So when we add two to an empty array we'll just get an array with the value two.
Similarly, when j is equal to one, the value is three, and when three is added to an empty array,
we'll have three over here.
And in a similar manner over here we have four.
And over here we have seven.
Now let's just draw out the recursion tree a bit more deeper.
And we are not going to draw the complete tree, but let's just draw it to a level which is sufficient
for us to understand the approach that we are discussing over here.
So how would this branch over here go down further in the question, it's mentioned that an element
can be taken multiple or an unlimited number of times.
So over here two is already added.
But we can again add two okay.
So the next level for this branch over here will be two comma two two comma three two comma four and
two comma seven.
So this would be the next level in this branch over here we can make an interesting observation.
Notice that this branch over here already has the values two and seven.
And when you add this up you get nine which is greater than seven.
So there is no point going down this branch further down because the value will only be greater than
nine.
But the target value itself is just seven.
So we can prune this branch over here.
So at any point, if the sum of the elements in coeur is going to be greater than the target value,
that branch will be pruned, and the next level over here would again be two comma two.
And then we add two, we add three, four and seven.
So it would look like this.
And the reason for this is that we can include two an unlimited number of times.
And these branches are going to be pruned because the sum of the values incur at these instances is
greater than seven.
Also notice over here, if you add two and two and three, you get the value seven which is the target
value.
Therefore, we can add this value of cur to the results array which will be finally returned.
And we don't need to go further down because we already found the combination of numbers that add up
to target.
Also notice if you were to go further down, you would get a value greater than target, right?
So there is no point going down further over here as well.
And then in this case again we would go down and we will add two to it three, four and seven.
And any instance where the sum of the elements incur is greater than target would be pruned.
And if we do get an instance where the sum of the values incur is equal to target, that would be added
to the results array, which is what we did over here as well.
Now again, we have just drawn out the recursion tree to some extent over here to get an idea of what's
happening over here.
Now there's one more interesting thing that you should notice or remember.
And for this, let's draw the next level for this branch over here.
So this is the instance where three is there in the current array and there's no other value.
So in the next level we will not be adding values from two onwards.
But rather we will only start from this index over here.
So three was the element at index one.
So in the next level for this branch we will start adding values only starting at index one.
So the next level for this would be three comma three, three comma four and three comma seven.
Now the reason for this is that if we had three comma two, notice that this is a repetition of this.
And because we don't want duplicates in this manner, that's why we will not have such a branch over
here.
But rather we will start at the index which is the value added over here.
So this would be three comma three, three comma four and three comma seven.
So the next level after this would be three comma three comma three.
And then you have three comma three comma four.
And you have three comma three comma seven.
And again it's another thing that these will be pruned.
Because the sum of the elements incur at each of these instances is greater than the target value,
which is equal to seven.
Also notice that when you have three comma four over here, this adds up to seven, which is the target
value.
And therefore this.
Over here, this instance of car will be added to the results array.
Or a copy of this would be added to the results array.
So this is how we can get all the combinations of elements in the candidates array, where an element
can be taken an unlimited number of times, such that the values in the combination adds up to the target
value which is given to us.
And notice that this is a backtracking approach because the changes to occur are made in place.
So for example, over here we see that this can be pruned.
And then we would remove this seven.
So we come back to this and then we would remove this two.
So the current array again would be an empty array.
And then we will add three to it.
So again notice this is a typical backtracking approach.