algorithm - Obtaining a powerset of a set in Java -

the powerset of {1, 2, 3} is:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

let's have set in java:

set<integer> myset = new hashset<integer>(); myset.add(1); myset.add(2); myset.add(3); set<set<integer>> powerset = getpowerset(myset); 

how write function getpowerset, best possible order of complexity? (i think might o(2^n).)

yes, o(2^n) indeed, since need generate, well, 2^n possible combinations. here's working implementation, using generics , sets:

public static <t> set<set<t>> powerset(set<t> originalset) {     set<set<t>> sets = new hashset<set<t>>();     if (originalset.isempty()) {         sets.add(new hashset<t>());         return sets;     }     list<t> list = new arraylist<t>(originalset);     t head = list.get(0);     set<t> rest = new hashset<t>(list.sublist(1, list.size()));      (set<t> set : powerset(rest)) {         set<t> newset = new hashset<t>();         newset.add(head);         newset.addall(set);         sets.add(newset);         sets.add(set);     }            return sets; }   

and test, given example input:

 set<integer> myset = new hashset<integer>();  myset.add(1);  myset.add(2);  myset.add(3);  (set<integer> s : setutils.powerset(myset)) {      system.out.println(s);  }