Java - Finding all subsets of a String (powerset) recursively

Question

So, I need to find all subsets of a given string recursively. What I have so far is:

static ArrayList<String> powerSet(String s){
        ArrayList<String> ps = new ArrayList<String>();
        ps.add(s);


        for(int i=0; i<s.length(); i++){
            String temp = s.replace(Character.toString(s.charAt(i)), "");
            ArrayList<String> ps2 = powerSet(temp);
            for(int j = 0; j < ps2.size(); j++){
                ps.add(ps2.get(j));
            }
        }   

        return ps;

I think I know what the problem is now, but I dont know how to fix it. Currently, I find all the power sets of temp, which are "bcd", "acd", "abd", "abc", which will cause duplicates. Any ideas on how to fix this?

By powerset, I mean if the string is abc, it will return "", "a", "b", "c", "ab", "ac", "bc", "abc".

Answer 1

The number of subsets of a set with n elements is 2ⁿ. If we have, for example, the string "abc", we will have 2ⁿ = 2³ = 8 subsets.

The number of states that can be represented by n bits is also 2ⁿ. We can show there is a correspondence between enumerating all possible states for n bits and all possible subsets for a set with n elements:

   2 1 0   2 1 0
   c b a    bits
0          0 0 0
1      a   0 0 1
2    b     0 1 0
3    b a   0 1 1
4  c       1 0 0
5  c   a   1 0 1
6  c b     1 1 0 
7  c b a   1 1 1

If we consider line 5, for example, bits 2 and 0 are active. If we do abc.charAt(0) + abc.charAt(2) we get the subset ac.

To enumerate all possible states for n bits we start at 0, and sum one until we reach 2ⁿ - 1. In this solution we will start at 2ⁿ - 1 and decrement until 0, so we don't need another parameter just to keep the number of subsets, but the effect is the same:

static List<String> powerSet(String s) {
    // the number of subsets is 2^n
    long numSubsets = 1L << s.length();
    return powerSet(s, numSubsets - 1);
}

static List<String> powerSet(String s, long active) {
    if (active < 0) {
        // Recursion base case
        // All 2^n subsets were visited, stop here and return a new list
        return new ArrayList<>();
    }

    StringBuilder subset = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        // For each bit
        if (isSet(active, i)) {
            // If the bit is set, add the correspondent char to this subset
            subset.append(s.charAt(i));
        }
    }
    // Make the recursive call, decrementing active to the next state,
    // and get the returning list
    List<String> subsets = powerSet(s, active - 1);
    // Add this subset to the list of subsets
    subsets.add(subset.toString());
    return subsets;
}

static boolean isSet(long bits, int i) {
    // return true if the ith bit is set
    return (bits & (1L << i)) != 0;
}

Then you just need to call it:

System.out.println(powerSet("abc"));

And get all 8 subsets:

[, a, b, ab, c, ac, bc, abc]

Answer 2

There is a way to do this without using recursion, it relies on a simple correspondence between bit strings and subsets.

So, assume you have a three character string "abc", then, as you noted, the subsets would be "", "c", "b", "bc", "a", "ac", "ab", "abc"

If you make a table of the characters and write a 1 for every character that is in the subset and 0 for not in the subset, you can see a pattern:

    a b c   bits    decimal
            0 0 0   0
        c   0 0 1   1
      b     0 1 0   2
      b c   0 1 1   3
    a       1 0 0   4
    a   c   1 0 1   5
    a b     1 1 0   6
    a b c   1 1 1   7

For each length-n string of unique characters, you will have 2ⁿ subsets, and you can generate them all by simply making one for loop from i=0 to i=2ⁿ-1, and includes only those characters corresponding to the bits in i that are 1.

I wrote a Java example here and a C example here.