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++) {

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

  • 4
    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. Commented Jun 15, 2012 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
    Commented Jun 15, 2012 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
    Commented Jun 15, 2012 at 10:10
  • @paulsmith: If you could, you'd have solved P = NP and you'd be a Nobel Prize-winning CS doctor.
    – DeadMG
    Commented Jun 15, 2012 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. Commented Jun 15, 2012 at 14:33

1 Answer 1


From what I understand this doesn't work. You wouldn't find "AC" in the set "ABCD" (i.e. holes). To find all subsets think that each element is either inside the subset or not. Which is basically a binary yes, no. Therefore you can cycle over all numbers with k 0/1 bits to find all combinations.

  • Yes you're right! I seem to have missed that use case. So how would you make the algorithm?
    – paul smith
    Commented Jun 15, 2012 at 10:05
  • 1
    I'd use an integer counter. In each iteration you iterate over all bits by checking if the number is odd/even and then you shift bits to the right (like divide by 2) and check again. This way you iterate over all bits of the counter and decide whether to include a particular element or not. The rest is up to you to find out ;)
    – Gere
    Commented Jun 15, 2012 at 10:28
  • 1
    @Gerenuk, you're over-complicating it. Consider a set S with n elements. Any subset of S may be represented exactly by an n-bit bitmap. To generate all possible subsets, generate all possible n-bit bitmaps, i.e., count from 0 to (2n)-1, inclusive. 0 represents the empty set, and (2n)-1 represents the full set. Commented Jun 15, 2012 at 10:34
  • 2
    @john: You a) didn't understand my algorithm written in non-technical terms which is exactly what you propose; and b) you still haven't solved the practical question of returning sets and not some encoded representation. Tech-talk alone is fruit-less.
    – Gere
    Commented Jun 15, 2012 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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