hi I could understand the space complexity comes from the result and the queue we use to keep track of intermediate results.

for the result, the space complexity is O(2^N).

for the queue, it’s O(2^(N-1)).

sum them up, the space complexity is O(2^N). where does the ‘N*’ come from?

really appreciate your help. thanks!

It comes from the fact that each element in the results (and in the queue) has a length of O(n).

1 Like