Finding all the subsets of a set

by

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

More Related Contents:

  1. Creating all possible k combinations of n items in C++
  2. Fast ceiling of an integer division in C / C++
  3. Most efficient/elegant way to clip a number?
  4. Fastest algorithm for primality test [closed]
  5. Special simple random number generator
  6. sine wave that slowly ramps up frequency from f1 to f2 for a given time
  7. Efficiently getting all divisors of a given number
  8. Inverting a 4×4 matrix
  9. Fastest way to get the integer part of sqrt(n)?
  10. Finding square root without using sqrt function?
  11. Mixing two arrays by alternating elements two by two
  12. banker’s algorithm in c++
  13. What is the difference between palindrome permutation and permutation? [closed]
  14. Why does my code work? Simple arithmetics
  15. All Possible Combinations of a list of Values
  16. Sorting zipped (locked) containers in C++ using boost or the STL
  17. Can’t make value propagate through carry
  18. How does photoshop blend two images together? [closed]
  19. Power by squaring for negative exponents
  20. Uses of a C++ Arithmetic Promotion Header
  21. C++ Efficiently Calculating a Running Median [duplicate]
  22. The intersection of two sorted arrays
  23. Finding nearest point in an efficient way
  24. Fast n choose k mod p for large n?
  25. Convert string to mathematical evaluation [closed]
  26. Print 2-D Array in clockwise expanding spiral from center
  27. std::back_inserter for a std::set?
  28. How to rotate a N x N matrix by 90 degrees? [closed]
  29. OpenSouce C/C++ Math expression parser Library [closed]
  30. Is there any advantage to using pow(x,2) instead of x*x, with x double?

Leave a Comment