In the previous video, we have discussed the approach for solving the combinations.
Sum one question.
Now let's try to think about the space and time complexity of this approach.
If n is the number of candidates in the candidates array which is given to us, and if T is the target
value, and if M is the minimum value among the candidates or the integers in the candidates array.
For example, over here, two is the minimum value.
So if M is the minimum value among the candidates, then notice that for the recursion tree, the maximum
depth would be equal to t divided by m.
Now why is that the case.
Because notice over here for example two was the minimum value.
So initially we added two.
Then we again added two over here.
And again we add two over here.
And in the next level we would again add one more time two.
And at this point two plus two plus two plus two is equal to eight.
And eight is greater than the target value which is seven.
So this branch over here would be pruned.
But this would be the branch which has the greatest depth.
So that's why the maximum depth of the tree would be equal to t divided by m.
Because in this case we are adding the lowest value till either we get the sum to be equal to the target
value, or the sum to be greater than the target value.
Now again for example, target could have been eight, and in that case two plus two plus two plus two
would be equal to eight.
And we would stop going down further or in.
As you can see over here this sum is eight which is greater than seven.
So this would give us or t by m will give us the maximum depth of the tree.
And that is the case because we are adding the least value t by m times till the sum of the elements
in the current array is equal to the target value, or greater than the target value.
Coming back to what we are trying to do over here, we are trying to find the space and time complexity
of the approach that we have previously discussed.
And for this, we are trying to find the number of nodes, or the upper bound of the number of nodes
in the recursion tree over here.
Because if we know that we can make use of that to find the time and space complexity.
So we have seen that the maximum depth of the tree or the recursive tree is t divided by m.
Now let's see how we can use this to find the upper bound of the number of nodes in this tree.