Complexity when generating all combinations
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?
Answer
First, there is nothing wrong with using O(n! / (n-k)!k!) - or any other function f(n) as O(f(n)), but I believe you are looking for a simpler solution that still holds the same set.
If you are willing to look at the size of the subset k as constant,
for k<=n-k:
n! / ((n-k)!k!) = ((n-k+1) (n-k+2) (n-k+3) ... n ) / k!
But the above is actually (n^k + O(n^(k-1))) / k!, which is in O(n^k)
Similarly, if n-k<k, you get O(n^(n-k))
Which gives us O(n^min{k,n-k})