5
$\begingroup$

We are given a set of $n$ elements and we'd like to generate all $k$-subsets of this set. For example, if $S=\{1,2,3\}$ and $k=2$, then the answer would be $\{1,2\}, \{1,3\}, \{2,3\}$ (order not important).

There are $\binom{n}{k}$ $k$-subsets of an $n$-set (by definition :-), which is $O(n^k)$ (although this is not tight). Obviously any algorithm for the problem will have to run in time $\Omega(\binom{n}{k})$.

What is the currently fastest known algorithm for this problem? Can the lower bound of $\binom{n}{k}$ actually be achieved (so that we have an essentially optimal algorithm)?

(Note: I reposted this from StackOverflow as the question seems better suited for CS StackExchange.)

$\endgroup$
4
$\begingroup$

Knuth's Algorithm R Revolving-Door combinations is generally accepted as the current best for algorithms and time complexity for generating combinations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.