Finding all the subsets of a set

c++ algorithm math subset
Rahul Vyas picture Rahul Vyas · Apr 8, 2009 · Viewed 113.1k times · Source

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}

Answer

Michael Borgwardt picture Michael Borgwardt · Apr 8, 2009

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

Related questions

Fast ceiling of an integer division in C / C++

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3. The …

Read More
Creating all possible k combinations of n items in C++

There are n people numbered from 1 to n. I have to write a code which produces and print all different combinations of k people from these n. Please explain the algorithm used for that.

Read More
Finding square root without using sqrt function?

I was finding out the algorithm for finding out the square root without using sqrt function and then tried to put into programming. I end up with this working code in C++ #include <iostream> using namespace std; double …

Read More