Finding all the subsets of a set

Question

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 examples 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 Make a Simple Function in c++ to find subsets of {1,2,3,4,5}

Answer 1

You may want to google for powerset.

Answer 2

Here's a related post:

Algorithm to return all combinations of k elements from n

Answer 3

If you want to enumerate all possible subsets have a look at this paper. They discuss different approaches such as lexicographical order, gray coding and the banker's sequence. They give an example implementation of the banker's sequence and discuss different characteristics of the solutions e.g. performance.

Answer 4

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

Answer 5

one simple way would be the following pseudo code:

Set getSubsets(Set theSet)
{
  SetOfSets resultSet = theSet, tempSet;


  for (int iteration=1; iteration < theSet.length(); iteration++)
    foreach element in resultSet
    {
      foreach other in resultSet
        if (element != other && !isSubset(element, other) && other.length() >= iteration)
          tempSet.append(union(element, other));
    }
    union(tempSet, resultSet)
    tempSet.clear()
  }

}

Well I'm not totaly sure this is right, but it looks ok.

Answer 6

You dont have to mess with recursion and other complex algorithms. You can find all subsets using bit patterns (decimal to binary) of all numbers between 0 and 2^(N-1). Here N is cardinality or number-of-items in that set. The technique is explained here with an implementation and demo.

http://codeding.com/?article=12

Answer 7

Here is a solution in Scala:

def subsets[T](s : Set[T]) : Set[Set[T]] = 
  if (s.size == 0) Set(Set()) else { 
    val tailSubsets = subsets(s.tail); 
    tailSubsets ++ tailSubsets.map(_ + s.head) 
}