Finding the powerset of a String

Question

I'm trying to write a java method for finding the subset of a string but I keep getting a runtime error I have been unable to debug. Here is the code:

public static List<String> subset(String m, List<String> list){
    if (m.length() <= 1){
        list.add(m);
        return list;
    }
    else{
        String letter = m.substring(0,1);
        String rest = m.substring(1,m.length());
        for (String x : subset(rest,list)){
            list.add(letter + x);

        }

        list.add(letter);
        return list;
    }
}

Answer 1

Your problem is that in your for loop, you're iterating through a list that's constantly changing. This gives you a ConcurrentModificationException.

It's better if you make a copy of your list first, before you try to iterate through it. You want something like this in place of your for loop.

List<String> copy = new ArrayList<String>(subset(rest,list));
for (String x : copy){
   list.add(letter + x);
}

This works, of course (yes, I've tested it), but it's a bit confusing in the way that you've added SOME elements by recursion and OTHERS by iteration. I think a re-design would be a good idea.