Let's now take a look at the space and time complexity of the approach that we have discussed for solving
combination sum two.
Now, in combination sum two, it's mentioned that each candidate can be used only one time.
And that's why we can say that the upper bound of the time complexity involved will be of the order
of two to the power n.
Now, why is this the case?
This is the case over here because we have n elements in the candidates array.
And for each element we can make two possible decisions, which is to either include the element or
exclude the element.
Now in the code or in the approach that we have discussed, the including part is taken care by appending
to the current array, and the excluding part is implicitly taken care when we move to the next index.
So this is why there can be up to two to the power n paths, and therefore the time complexity of this
solution is going to be of the order of two to the power n.
What about the space complexity?
The space complexity of this approach is going to be of the order of n.
Now why is that the case?
So what are the things that take up space or auxiliary space in the approach that we have discussed.
So we will have space taken up on the recursive call stack.
And the maximum space over there which is taken up will be of the order of N.
And we will also take up space for the hash map.
And again, in the worst case, if we store all the elements in the hash map, the space used up in
the hash map can be of the order of n.
So that's why the space complexity also of this solution is of the order of n.