Complexity to generate every combination of every size for a given sequence
Each element in the sequence is part of the combination or not (a binary choice). Since there are $n$ elements, this gives $2^n$ possible combinations.

Using a gray code to iterate over the elements we can make sure that we iterate over every possible combination by only putting in or taking out a single element every time. 

Assuming your elements are numbered $1\dots n$ we can use the following algorithm. If our current combination $C_k$ contains an even amount of elements, toggle element $1$ to get $C_{k+1}$. Otherwise, toggle element $\min(C_k)+1$ to get $C_{k+1}$.

Starting from the empty combination $\{\}$ we get:

\begin{matrix}
\{\} &amp; \text{even} &amp; \text{toggle $1$}\\
\{1\} &amp; \text{odd} &amp; \text{toggle $\min(\{1\}) + 1$}\\
\{1, 2\} &amp; \text{even} &amp; \text{toggle $1$}\\
\{2\} &amp; \text{odd} &amp; \text{toggle $\min(\{2\}) + 1$}\\
\{2, 3\}  &amp; \text{even} &amp; \text{toggle $1$}\\
\{1, 2, 3\} &amp; \text{odd} &amp; \text{toggle $\min(\{1, 2, 3\}) + 1$}\\
\{1, 3\}  &amp; \text{even} &amp; \text{toggle $1$}\\
\{3\} &amp; \text{odd} &amp; \text{toggle $\min(\{3\}) + 1$}\\
\cdots &amp; \cdots &amp;\cdots
\end{matrix}

By separately storing whether we are currently even/odd and flipping it, and storing our combination in sorted order we can always get to the next combination in $O(1)$ time. So it simply takes $O(2^n)$ time to generate all combinations.