# Complexity to generate every combination of every size for a given sequence

I would like to estimate complexity in space and time of generating every combination of every size for a given sequence.

Exemple :

 seq = [1,2,3]
combinations = [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]


From what i know, for a given sequence of size n and a fixed combination size k, the number of combination generated is ${n}\choose{k}$, so i suppose than complexity in time and space is $O({{n}\choose{k}})$.

What we want is the sum for every value of $k$, $O({\sum_{i=1}^n{{n}\choose{i}}})$

I know that for a sum the complexity equals to the most complex element of the sum.

For the binomial coefficient, if n is even, the biggest one will be $n \choose \frac{n}{2}$

So i can put a an upper born as $O(n.{n \choose \frac{n}{2}})$

Is there a more precise way to determine the complexity of this operation ?

• It seems that you are trying to generate all the non-empty subsets of given set $S$. If $S$ has $n$ elements, there're $2^n - 1$ non-empty different subsets, so a lower bound would be $2^n - 1$.
– sel
Jul 20, 2017 at 9:14
• The number of subsets of a set of size $n$ is $2^n$. Depending on your computation model, you should be able to generate all sets in $O(n2^n)$ or better. Jul 20, 2017 at 10:18
• Maybe this helps en.wikipedia.org/wiki/… Jul 20, 2017 at 10:29
• Maybe this would help.
– Evil
Jul 21, 2017 at 3:14

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.
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} \{\} & \text{even} & \text{toggle $1$}\\ \{1\} & \text{odd} & \text{toggle $\min(\{1\}) + 1$}\\ \{1, 2\} & \text{even} & \text{toggle $1$}\\ \{2\} & \text{odd} & \text{toggle $\min(\{2\}) + 1$}\\ \{2, 3\} & \text{even} & \text{toggle $1$}\\ \{1, 2, 3\} & \text{odd} & \text{toggle $\min(\{1, 2, 3\}) + 1$}\\ \{1, 3\} & \text{even} & \text{toggle $1$}\\ \{3\} & \text{odd} & \text{toggle $\min(\{3\}) + 1$}\\ \cdots & \cdots &\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.