Time complexity of a recursive function which generates all combinations of an array
Denote by $T(n)$ the running time of your function on an input of length $n$, assuming that all operations are $O(1)$. Then $T(0) = O(1)$, and for $n &gt; 0$,
$$
T(n) = O(n) + \sum_{m=0}^{n-1} T(m).
$$
Let us replace $O(n)$ with $Cn$. Then
$$
T(n) - T(n-1) = Cn + \sum_{m=0}^{n-1} T(m) - C(n-1) - \sum_{m=0}^{n-2} T(m) = C + T(n-1),
$$
and so $T(n) = 2T(n-1) + C$, implying that $T(n) + C = 2(T(n-1) + C)$. Therefore $T(n) = 2^n(T(0) + C) - C = O(2^n)$.