Let's now get into the code for solving combination sum one.
Okay, so let's first take a look at the skeleton of the code that we have over here.
And then let's get into the details.
So as the question asks we need to identify a set of numbers from the candidates array such that the
values add up to the target value.
And in the question it's also given that the candidates array has only non negative values.
Okay.
And it's also mentioned in the question that we can include a number from the candidates array multiple
times.
So this is given in the question.
So over here we have followed a recursive approach for solving this question.
So we have used the helper function.
And we have called the helper function combination some recursive.
And we are calling the helper function for the first time over here.
And we also have declared an array rest over here.
And at every point when we identify a combination of values from the candidates array such that the
values add up to target, we make a copy of that particular combination, and we push it to the results
array over here.
And finally we return the results array.
So this is the skeleton of the approach that we have over here.
Now let's take a look at the details.
So to the helper function notice that the things that are passed to it are the starting index okay.
So that's what we have over here.
And we have an array over here which we are passing to the helper function to track the current state.
Because we need something to track what the combination of elements looks like at any point.
So for that we have this array.
And then we also have a value which indicates the current sum of the elements which have been added
to cur.
So these are the three things that we are passing to the helper function.
And initially when we call the helper function, the values that we pass to it are zero.
Because obviously we have to start at the first index of the candidates array.
And at this point CR is just an empty array, and the sum of the values in the current array is zero
because nothing has been added to it.
All right.
Now let's go a little bit deeper.
So over here let's take a look at the helper function in detail.
So first of all we have the base case over here.
Notice that if cur sum at any point is greater than the target then we just return.
This is so because it's given that the values in the candidates array are non-negative.
So if at any point already the sum of the values added to cur is greater than target, then by adding
more values to it which are non negative, we will just keep increasing the sum and we would not be
able to decrease the sum because there are no negative values in the candidates array.
So that's why if cur sum is greater than target, we can just return.
And on the other hand, if at any point we see that cur sum is equal to target, then we have identified
a set of values from the candidates array in a manner that the values add up to the target value, and
therefore we make a copy of cur at this point and we push it to the results array.
Now again we make a copy and push it, because at a later stage cur will keep changing because we are
making changes to cur in place.
We are not making new arrays at every point we are using the same cur array, and we are just trying
to identify all the possible combinations of elements from the candidates array that add up to target.
So that's why we make a copy of Cur over here and we push it to the results array.
So this over here is the base case.
Now what about the recursive case.
So we have the recursive case over here.
So if none of these is true then we have a variable j which takes the values from index up to the last
valid index in the candidates array okay.
And for each value of j we just push it to cur.
And we call the helper function recursively.
And notice in this recursive call we still pass the start index as j itself, because in the question
it's mentioned that a value can be used multiple times.
So that's why again we pass the index j itself, even though we have just now included the value at
index J Tucker.
Okay.
So that's why we have J over here.
And then we increment the sum because a new value has been added to Kur.
And we also pass Kur to the helper function.
And once we come out of this we do the backtracking step which is to pop the value that we just added
to the Kur array.
So this is how we can solve combination sum one.
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.
Again, do make use of the user logs in case you're stuck and you want some help to debug your code.