Finding all the subsets of a set

I need an algorithm to find all of the subsets of a set where the number of elements in a set is n.

S={1,2,3,4...n}

Edit: I am having trouble understanding the answers provided so far. I would like to have step-by-step explanation of how the answers work to find the subsets.

For example,

S={1,2,3,4,5}

How do you know {1} and {1,2} are subsets?

Could someone help me with a simple function in c++ to find subsets of {1,2,3,4,5}

It's very simple to do this recursively. The basic idea is that for each element, the set of subsets can be divided equally into those that contain that element and those that don't, and those two sets are otherwise equal.

For n=1, the set of subsets is {{}, {1}}
For n>1, find the set of subsets of 1,...,n-1 and make two copies of it. For one of them, add n to each subset. Then take the union of the two copies.

Edit To make it crystal clear:

The set of subsets of {1} is {{}, {1}}
For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}
Repeat till you reach n

Too late to answer, but an iterative approach sounds easy here:

1) for a set of n elements, get the value of 2^n. There will be 2^n no.of subsets. (2^n because each element can be either present(1) or absent(0). So for n elements there will be 2^n subsets. ). Eg:
for 3 elements, say {a,b,c}, there will be 2^3=8 subsets

2) Get a binary representation of 2^n. Eg:
8 in binary is 1000

3) Go from 0 to (2^n - 1). In each iteration, for each 1 in the binary representation, form a subset with elements that correspond to the index of that 1 in the binary representation. Eg:

For the elements {a, b, c}
000 will give    {}
001 will give    {c}
010 will give    {b}
011 will give    {b, c}
100 will give    {a}
101 will give    {a, c}
110 will give    {a, b}
111 will give    {a, b, c}

4) Do a union of all the subsets thus found in step 3. Return. Eg:
Simple union of above sets!

In case anyone else comes by and was still wondering, here's a function using Michael's explanation in C++

vector< vector<int> > getAllSubsets(vector<int> set)
{
    vector< vector<int> > subset;
    vector<int> empty;
    subset.push_back( empty );

    for (int i = 0; i < set.size(); i++)
    {
        vector< vector<int> > subsetTemp = subset;  //making a copy of given 2-d vector.

        for (int j = 0; j < subsetTemp.size(); j++)
            subsetTemp[j].push_back( set[i] );   // adding set[i] element to each subset of subsetTemp. like adding {2}(in 2nd iteration  to {{},{1}} which gives {{2},{1,2}}.

        for (int j = 0; j < subsetTemp.size(); j++)
            subset.push_back( subsetTemp[j] );  //now adding modified subsetTemp to original subset (before{{},{1}} , after{{},{1},{2},{1,2}}) 
    }
    return subset;
}

Take into account though, that this will return a set of size 2^N with ALL possible subsets, meaning there will possibly be duplicates. If you don't want this, I would suggest actually using a set instead of a vector(which I used to avoid iterators in the code).

Finding all the subsets of a set

Related

Recent Posts