I'm trying to find a way to find all subsets of a set.

Is there an algorithm to calculate this?

  • 9
    $\begingroup$ Is the set finite? $\endgroup$ Commented Apr 2, 2013 at 16:24
  • 3
    $\begingroup$ Hint: in any given subset, each member of the base set is either in the subset or not in it. Can you think of a convenient way to map this to a digital representation? $\endgroup$ Commented Apr 2, 2013 at 16:24
  • $\begingroup$ List them one by one? $\endgroup$
    – Hui Yu
    Commented Apr 2, 2013 at 16:26
  • 2
    $\begingroup$ In general, there is not even an algorithm to find all elements of a set. $\endgroup$ Commented Apr 2, 2013 at 16:29
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Power_set $\endgroup$ Commented Apr 2, 2013 at 16:34

10 Answers 10


The algorithm in a recursive one. To understand the algorithm consider the following example:

Let $S = \{1,2,3\}$. The subsets of $S$ are all subsets of $\{1,2\}$ and all subsets of $\{1,2\}$ with the element $3$ appended to each subset. Essentially, if you know subsets of $\{1,2\}$, the problem can be solved. You can take it from here on.

  • $\begingroup$ What is the name of this algorithm? $\endgroup$
    – user346461
    Commented Jun 11, 2016 at 19:52

An alternative to the recursive formulations provided so far to enumerate the subsets of a finite set is to index the subsets : if $n$ is the number of elements of your set, there are $2^n$ subsets. The subsets can be enumerated iteratively by using a variable index ranging from $0$ to $2^n-1$, and using the binary representation of the variable index to determine which elements of your base set the current subset has.

Over recursive formulations, this one has the advantage of not risking a stack overflow, which may happen if $n$ is greater than the stack capacity. It also avoids storing lists of subsets if you can process these subsets with a continuation.

  • 1
    $\begingroup$ While I didn't want to give a direct answer to what feels quite strongly like a homework question, this is a much better answer than any recursive or combination-based approach. $\endgroup$ Commented Apr 2, 2013 at 16:56
  • $\begingroup$ @StevenStadnicki I fear the homework question as well, and tried not to be too descriptive, I hope this is not going too far. I had not read your comment when I started writing this, however all credit should go to you. $\endgroup$ Commented Apr 2, 2013 at 16:58
  • $\begingroup$ This is a common interview question. Got asked this twice already. Just leaving a note. $\endgroup$
    – ninja123
    Commented Dec 30, 2016 at 15:10

In C, the algorithm explained by Vincent Nivoliers could look like:

int main(int size, char * set[]) {

    unsigned int i, j;
    unsigned short bit;
    unsigned int max_bits;  // max bits for number i
    size = size - 1;  // exclude first element

    for (i = 0; i < pow(2, size); i++) {
        printf("{ ");
        max_bits = floor( log2(i) );
        for (j = 0; j <= max_bits; j++) {
            bit = (i >> j) & 1;  // bit value at position j
            if (bit == 1)
                printf("%s ", set[j + 1]);  // one-based array, add 1
    return 0;

which would for the arguments 1 2 3 produce the output

{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }

The classic solution to this problem uses binary digits -- count from zero to $2^n-1$ where $n$ is the number of elements and for every value $k$ in the range include an element in the subset if the bit at position $q$ where $0\le q\le n-1$ is set.

Here is an implementation that prints all subsets of its command line arguments.

#! /usr/bin/perl -w

    my $n = scalar(@ARGV);

    my (@flags) = (0) x $n;

    my $pos;
      my @subset = ();
      for($pos=0; $pos<$n; $pos++){
          push @subset, $ARGV[$pos]
            if $flags[$pos] == 1;
      print '{' . join(', ', @subset) . '}';
      print "\n";

      for($pos=0; $pos<$n; $pos++){
          if($flags[$pos] == 0){
            $flags[$pos] = 1;

          $flags[$pos] = 0;

      last if $pos == $n;

This is what the output looks like:

$ ./subsets.pl a b c
{a, b}
{a, c}
{b, c}
{a, b, c}
  • $\begingroup$ This can also be done by directly counting to $2^n-1$ and extracting the bits of $k$ one after the other, but the idea is exactly the same. $\endgroup$ Commented Apr 2, 2013 at 21:52

By identifying subsets with characteristic vectors, enumerating all subsets of an $n$-element set is the same as enumerating all binary vectors of length $n$.

One way is to enumerate the numbers $0,1,\ldots,2^n-1$ in binary notation. In many situations it is desirable to flip only a single bit going from one element to the next (correspondingly, going from one subset to the next by adding or removing only a single element). This can be achieved by the Gray code.

  • $\begingroup$ I believe you mean $2^n-1$ rather than $n-1$ at the start of your second paragraph... $\endgroup$ Commented Apr 2, 2013 at 22:31
  • $\begingroup$ @StevenStadnicki: Thanks for spotting this. It is corrected now. $\endgroup$
    – azimut
    Commented Apr 3, 2013 at 8:13

In a very simple speech, with binary codes you can discover all of them. for example if you want to write all subsets of a set with 2 member , you must calculate whole number from 0 to (2^2)-1 or 3. For instance: Suppose set : {1,2}

00 -----> 0 ---> {}
01 -----> 1 ---> {1}
10 -----> 2 ---> {2}
11 -----> 3 ---> {1,2}

and you can continue this to end.


Considering the set to be finite with $n$ elements in them.

Let $A$ = $(a_1, a_2,...a_n$)

Now you can have subsets of size $0$ to $n$ elements.

If the number of elements is ($n-1$) , subsets of $(n-1)$ element-ed sets are subsets of $A$ itself. This can be extended till $1$ element subsets.


You can make the $0,1, \dots n$ sets with the given elements.


An algorithm is type of finite procedure operating on finite data as input and generating a finite output. So you can only have an algorithm to find the subsets of $\Sigma$ if $\Sigma$ is finite. (You've been given some hints for that case, but it is important to stress that these hints only work for finite $\Sigma$.)


If I look into the problem in another perspective, this eventually boils down to

$$\sum_{k=0}^{|S|} {{|S|}\choose{k}}$$

And quickly solving in Python

>>> S = {1,2,3,4}
>>> from itertools import chain, combinations
>>> list(chain(*(list(combinations(S, n)) for n in range(0, len(S)+1))))
[(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]

First, you should notice that the only subset of an empty set is the empty set itself.


  1. Fix some element x of the set.
  2. Generate all subsets of the set formed by removing x from the main set.
  3. These subsets are subsets of the original set.
  4. All of the sets formed by adding x into those subsets are subsets of the original set.

Following is an illustration:

{ A, H, I}

{ H, I}

{ I}

{ }

now, we reach the base situation, namely empty set. Then, we will add the x that we have fixed into those subsets:

{ A, H, I} ------------------------> {A,H,I},{A,H},{A,I},{A}


{ H, I} ------------------------> {H, I}, {H},

                      {I}, {}

{ I} ------------------------> {I}, {}

{ } ------------------------> {}

source: http://www.stanford.edu/class/archive/cs/cs106b/cs106b.1126/lectures/07/Slides07.pdf


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .