Obtaining a powerset of a set in Java
Yes, it is O(2^n) indeed, since you need to generate, well, 2^n possible combinations. Here’s a working implementation, using generics and 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 … Read more