C++ Power Set
Posted by Samath
Last Updated: January 05, 2017
  2309

A Power Set is a set of all the subsets of a set.

For Example:

For the set {a,b,c}:
- These are subsets: {a}, {b} and {c}
- And these are subsets: {a,b}, {a,c} and {b,c}
- And {a,b,c} is also a subset of {a,b,c}
- And the empty set {} is a subset of {a,b,c}

#include <iostream>
#include <string>
#include <set>
using namespace std;

#define ARRAY_SIZE(array) (sizeof((array))/sizeof((array[0])))

set<string> Pend(set<string>  s, string ss)
{
  set<string>:: iterator it = s.begin();
  set<string> res;
  res.insert(ss);
  for(it ; it != s.end(); it++)
  {
      string temp = *it;
      res.insert(temp);
      temp+= ss;
      res.insert(temp);
  }
  
  return res;
}

set<string> PowerSet(set<string> s)
{
  if(s.empty() || s.size() == 1)
  {
    return s;    
  }
  set<string>::iterator it = s.begin();
  string temp = *it;
  s.erase(it);
  s = PowerSet(s);
  s = Pend(s,temp);
  return s;
}

int main ()
{
  
  string s[] = {"a","b","c","d","e","f"};

  set<string> strs;
  strs.insert(s,s+ARRAY_SIZE(s));

  strs = PowerSet(strs);
  set<string>::iterator it = strs.begin();
  cout << "PowerSet size: " << strs.size() <<endl;
  for(it; it != strs.end() ; it++)
  {
    cout << *it << " ";     
  }
  
  return 0;
}