1
00:00:00,110 --> 00:00:07,070
Let's now take a look at the space and time complexity of the approach that we have discussed for solving

2
00:00:07,070 --> 00:00:08,450
combination sum two.

3
00:00:08,480 --> 00:00:15,320
Now, in combination sum two, it's mentioned that each candidate can be used only one time.

4
00:00:15,320 --> 00:00:22,130
And that's why we can say that the upper bound of the time complexity involved will be of the order

5
00:00:22,130 --> 00:00:23,690
of two to the power n.

6
00:00:23,720 --> 00:00:25,580
Now, why is this the case?

7
00:00:25,610 --> 00:00:31,190
This is the case over here because we have n elements in the candidates array.

8
00:00:31,190 --> 00:00:38,270
And for each element we can make two possible decisions, which is to either include the element or

9
00:00:38,270 --> 00:00:39,650
exclude the element.

10
00:00:39,680 --> 00:00:46,430
Now in the code or in the approach that we have discussed, the including part is taken care by appending

11
00:00:46,460 --> 00:00:55,220
to the current array, and the excluding part is implicitly taken care when we move to the next index.

12
00:00:55,220 --> 00:01:01,700
So this is why there can be up to two to the power n paths, and therefore the time complexity of this

13
00:01:01,700 --> 00:01:05,420
solution is going to be of the order of two to the power n.

14
00:01:05,660 --> 00:01:07,730
What about the space complexity?

15
00:01:07,760 --> 00:01:12,890
The space complexity of this approach is going to be of the order of n.

16
00:01:12,890 --> 00:01:14,570
Now why is that the case?

17
00:01:14,570 --> 00:01:20,240
So what are the things that take up space or auxiliary space in the approach that we have discussed.

18
00:01:20,240 --> 00:01:25,130
So we will have space taken up on the recursive call stack.

19
00:01:25,130 --> 00:01:29,930
And the maximum space over there which is taken up will be of the order of N.

20
00:01:31,330 --> 00:01:34,750
And we will also take up space for the hash map.

21
00:01:34,750 --> 00:01:40,960
And again, in the worst case, if we store all the elements in the hash map, the space used up in

22
00:01:40,960 --> 00:01:43,450
the hash map can be of the order of n.

23
00:01:43,450 --> 00:01:48,910
So that's why the space complexity also of this solution is of the order of n.