Observe that:

$T(N) = 2T(N-1) + 2^{N-1}$

$T(1) = 2$

Note that the entire runtime, our algorithm only spends time generating more data. Therefore, our function T represents both the amount of time that the function spends running on an input of size T, and also the amount of data it generates.

We have $2T(N-1)$ because we first make the recursive call, and the following line makes a copy of all that data again in preparation to tack on the element we left out in the recursive call. We tack on exactly $2^{N-1}$ copies of the element we intentionally left out so that's where the last term comes from. Finally, T(1)=2 because with 1 element, we return 2 possible subsets (the entire set and the empty set).

Unrolling this recurrence we have:

$T(N)=2T(N-1)+2^{N-1}$

$\quad \quad =2(2(T(N-2)+2^{N-2})+2^{N-1}$

$\quad \quad =2(2(2(T(N-3)+2^{N-3})+2^{N-2})+2^{N-1}$

$...$

$\quad \quad = 2^N + (N-1)*2^{N-1}$

$\quad \quad = O(N*2^N)$

Observe that:

$T(N) = 2T(N-1) + 2^{N-1}$

$T(1) = 2$

Note that the entire runtime, our algorithm only spends time generating more data. Therefore, our function T represents both the amount of time that the function spends running on an input of size N, and also the amount of data it generates from an input of size N.

We have $2T(N-1)$ because we first make the recursive call, and the following line makes a copy of all that data again in preparation to tack on the element we left out in the recursive call. We tack on exactly $2^{N-1}$ copies of the element we intentionally left out so that's where the last term comes from. Finally, T(1)=2 because with 1 element, we return 2 possible subsets (the entire set and the empty set).

Unrolling this recurrence we have:

$T(N)=2T(N-1)+2^{N-1}$

$\quad \quad =2(2(T(N-2)+2^{N-2})+2^{N-1}$

$\quad \quad =2(2(2(T(N-3)+2^{N-3})+2^{N-2})+2^{N-1}$

$...$

$\quad \quad = 2^N + (N-1)*2^{N-1}$

$\quad \quad = O(N*2^N)$