Finding all subsets of a set (PowerSet)

Question

I want to find all subsets of a given set. I got string set defined as following: HashSet<String> L and I want to use in a loop all of its subsets as: for each do something. Is there an easy way with low complexity to do that?

Take a look here (which is the first result for googling "powerset in java") -> http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java — blgt, Sep 14 '13 at 11:02

score 12 · Answer 1 · answered Sep 14 '13 at 13:47

OK, I used this algorithm (L is a set of strings):

powerSet = new HashSet<List<String>>();
List<String> mainList = new ArrayList<String>(L);
buildPowerSet(mainList,mainList.size());

And,

private static void buildPowerSet(List<String> list, int count)
{
    powerSet.add(list);

    for(int i=0; i<list.size(); i++)
    {
        List<String> temp = new ArrayList<String>(list);
        temp.remove(i);
        buildPowerSet(temp, temp.size());
    }
}

score 3 · Answer 2 · answered Sep 14 '13 at 11:12

So you want to find all non empty SubSets of a Set, which would be {a}{b}{ab} for the set {ab}? Maybe not the fastest solution, but you could go through all elements in your set one by one, start with the first one, and determine all non empty sets -> the first element, go to the second element and copy all sets stored so far and add to all copied ones the new element plus and a new set with only the new element. Now you have all subsets of the previous elements plus a set of all those sets with the extra element added plus one with the new element alone. This can then be repeated for all elements and should give all non empty subsets.

Set<String> inputSet = new HashSet<String>();

inputSet.add("a");
inputSet.add("b");
inputSet.add("c");
inputSet.add("d");

List<Set<String>> subSets = new ArrayList<Set<String>>();
for(String addToSets:inputSet) {
    List<Set<String>> newSets = new ArrayList<Set<String>>();
    for(Set<String> curSet:subSets) {
        Set<String> copyPlusNew = new HashSet<String>();
        copyPlusNew.addAll(curSet);
        copyPlusNew.add(addToSets);
        newSets.add(copyPlusNew);
    }
    Set<String> newValSet = new HashSet<String>();
    newValSet.add(addToSets);
    newSets.add(newValSet);
    subSets.addAll(newSets);
}

for(Set<String> set:subSets) {
    for(String setEntry:set) {
        System.out.print(setEntry + " ");
    }
    System.out.println();
}

Which would output:

d 
d b 
b 
d c 
d b c 
b c 
c 
d a 
d b a 
b a 
d c a 
d b c a 
b c a 
c a 
a

Finding all subsets of a set (PowerSet)

2 Answers2