# faster algorithm for finding all subsets

This is the algorithm (pseudocode) I have right now for finding all subsets for a given set with length k:

``````void allSubsets(set[]) {
for (i = 0; i<k; i++) {
for (j = i + 1; j<k; j++) {
print(set[i...j]);
}
}
}
``````

But it's run-time is O(n^2). Can anybody improve this?

-
O(n^2) is better than possible, because there are `\binom{n}{k}` subsets of size k. For fixed k, you're looking at O(n^k) being optimal. – Peter Taylor Jun 15 '12 at 9:35
The number of subsets is 2^n, so it's impossible for algorithm to be better than O(2^n) - because it has to create the output at least. – user281377 Jun 15 '12 at 10:02
I see, so what you're saying is we can't do any clever tricks to avoid O(2^n). Right? – paul smith Jun 15 '12 at 10:10
@paulsmith: If you could, you'd have solved P = NP and you'd be a Nobel Prize-winning CS doctor. – DeadMG Jun 15 '12 at 10:24
Better than O(2^n) is possible for fixed k. I don't think anyone will give a better answer than the accepted one for stackoverflow.com/questions/127704/… , but I can't flag this question as a duplicate of a question on StackOverflow. – Peter Taylor Jun 15 '12 at 14:33