// subsets.h
// Eric Aubourg         CEA/DAPNIA/SPP   octobre 1999

#ifndef SUBSETS_H
#define SUBSETS_H

template <class T>
 set<set<T> > getSetOfSubsets(set<T> const&);
 
 
template <class T>
 set<set<T> > getSetOfSubsets(set<T> const& s) {
 set<set<T> > subsets;
 if (s.empty()) {
   subsets.insert(s);
   return subsets;
 }
 
 set<T> s1 = s; 
 T x = *(s1.begin());
 s1.erase(s1.begin());
 set<set<T> > sub1 = getSetOfSubsets(s1);
 subsets.insert(sub1.begin(), sub1.end());
 for (set<set<T> >::iterator i = sub1.begin(); i != sub1.end(); i++) {
   s1 = *i;
   s1.insert(x);
   subsets.insert(s1);
 }
 return subsets;
}

// subsets 1 2 3 :
//    subsets 2 3 :  {} {2} {3} {23}
//       + 1:        {1} {12} {13} {123}
 
 
#endif