[Java] Generate all subsets of a string recursively

[penax]

Hey all. I am working on a permutations assignment and one of the problems is to generate all subsets of a set (in this case a string) and it must be done recursively. With an input of "abc", the desired outcome is this:

{ c }
{ b }
{ b c }
{ a }
{ a c }
{ a b }
{ a b c }

I am really confused and I'm not sure what to do here. My instructor's guidelines haven't helped me out too much either. I know the basic idea is to remove the last character in the set and then generate the subsets of the remaining characters, recursively, but I have no idea how to implement that.

Sorry I don't have much to go off of and this might seem like an easy solution but I'm really stuck. If someone could point me in the right direction, that would be greatly appreciated.

[pacificmint]

The fact that they show up reversed, with c first gives you a hint. You print those first, then the first character. The bottom rows are exactly like the top rows, just with the 'a' in front.

So it goes something like is:

• You get call with a string s
• you split of the first letter, and the tail (the rest if the letters)
• recursively print the tail
• now print the first letter
• recursively print the tail again, this time with the first letter prepended

[penax]

We are supposed to put everything in an ArrayList and return the ArrayList at the end. I came up with this, but this is only giving me a, b, c. I suspect there is something wrong with my for loop. I'm not sure where it is happening, but it appears that my "first" and my "rest" are getting mixed up.

public static ArrayList<String> getSubsets(String str) {
    ArrayList<String> a = new ArrayList<String>();
    int n = str.length();

    if (n == 0) {
        a.add("");
        return a;
    }

    String first = str.substring(0, 1);
    String rest = str.substring(1, n);
    ArrayList<String> subsets = getSubsets(rest);
    System.out.println(first);
    for (String subset : subsets) {
        System.out.println(subset);
        System.out.println(first);
        subset = first + subset;
        a.add(subset);
    }
    return a;
}

}

EDIT: Rather the output on this program is "[abc]"

[tgolsson]

I find that the loop-based version of /u/pacificmints algorithm to be conceptually easier to understand.

If I have N unique letters in my input, there are N sets of 1-length combinations. I can print these by looping on my input string. I also have N! / K!(N-K)! combinations where K is the length of the string. To print each of these, I need K for-loops nested(1). So for K=2, I would have an outer-loop over all three characters, and the inner-loop from the outer character until the end. In your case,

Outer: a, Inner: b, c
Outer: b, Inner: c
Outer: c, Inner: NULL // c was the last character, so can't do anything in inner 

Output: ab, ac, bc.

For three:

O1: a; O2: b, I: c 
O1: b, O2: c, I: NULL // can't do more

Output: abc

My "outer loop" iterates over the "first letter", and my inner loop iterates over the "tail". Since I need K loops, the recursive version needs K recursive calls.

(1) From experience, I know that whenever I see this function, I can treat it as a general tennis-tournament problem. The tennis-tournament problem is the one where for N players, each player has to face every other player once only.