Interview questions where I start with "this might be solved by generating all possible combinations for the array elements" are usually meant to let me find something better.

Anyway I would like to add "I would definitely prefer another solution since this is O(X)".. the question is: what is the O(X) complexity of generating all combinations for a given set?

I know that there are n! / (n-k)!k! combinations (binomial coefficients), but how to get the big-O notation from that?