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.

Answer 3

I find it helpful to think of the simple corner cases first when designing a recursive algorithm, i.e. the empty string and the string with one character. Then you usually split the problem and make the recursive call on the rest/ tail of the string. Somewhat like this:

    static List<String> nuPowerSet(String s) {

    if (s.length() == 0) { // trivial, subset of empty string is empty
        return emptyList();
    }

    String head = s.substring(0, 1);
    if (s.length() ==1) // the subset of a one character string is exactly that character
        return asList(head);

    String tail = s.substring(1);

    ArrayList<String> ps = new ArrayList<String>();

    ps.add(head); // one of the subsets is the current first character


    List<String> tailSubsets = nuPowerSet(tail); // all the subsets of the remainder.

    List<String> tailSubsetsWithCurrentHeadPrepended = tailSubsets
            .stream()
            .map(element -> head + element) 
            .collect(Collectors.toList());

    ps.addAll(tailSubsets);
    ps.addAll(tailSubsetsWithCurrentHeadPrepended);

    return ps;
}

Answer 4

to eliminate duplicate, you just need to add all of them into a Set, this can be done easily with some sort of helper:

static ArrayList<String> powerSet(String s) {
    return new ArrayList<>(_powerSet(s));
}

static HashSet<String> _powerSet(String s) {
    HashSet<String> set = new HashSet<>();
    set.add(s);

    for(int i = 0; i < s.length(); i++) {
        String tmp = s.substring(0, i) + s.substring(i+1, s.length());
        set.addAll(_powerSet(tmp));
    }

    return set;
}

btw, your code has dealt with edge cases by nature. you don't need to worry about this.

Answer 5

You're right, you do have duplicates because you're creating temp multiple times (each time without another character) so when you're calling recursively there will be different subsets that will share the same characters and create the dup. For example, "abc" will create a temp with: ["ab", "ac", "bc"] and each one of them will call recursively with only one character so you'll get each one of "a", "b" and "c" twice.

One way to avoid it (with minimal changes) would be to use a Set instead of a list - which will omit all the dups:

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

    for (int i = 0; i < s.length(); i++) {
        String temp = s.replace(Character.toString(s.charAt(i)), "");
        Set<String> ps2 = powerSet(temp);
        for (String x : ps2) {
            ps.add(x);
        }
    }
    return ps;
}

Now the output will be:

bc
a
ab
b
ac
abc
c

A different solution:

public static List<String> powerset(String s) {
    List<String> ans = new LinkedList<>();
    if (null == s) {
        return ans;
    }
    return powerset(s, ans);
}

private static List<String> powerset(String s, List<String> ans) {
    if ("".equals(s)) {
        return ans;
    }
    String first = s.substring(0, 1);
    String rest = s.substring(1);
    ans.add(first);
    List<String> pAns = new LinkedList<>(ans);
    for (String partial : ans.subList(0, ans.size()-1)) {
        pAns.add(partial + first);
    }
    return powerset(rest, pAns);
}

OUTPUT

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

Answer 6

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;

    public class MainClass {

        static List<List<char[]>> list = new ArrayList<List<char[]>>();

        // static List<int[]> list1 = new ArrayList<int[]>();
        public static void main(String[] args) {
            List<char[]> list1 = new ArrayList<char[]>();
            String string = "abcd";
            char[] a = string.toCharArray();
            generate(a, 0, 0, list1);

            for (List<char[]> l : list) {
                for (char[] b : l) {
                    for (char c : b) {
                        System.out.print(c + ",");
                    }
                    System.out.println();
                }
            }

        }

        public static void generate(char[] array, int offset, int index, List<char[]> list1) {
            if (offset >= array.length)
                return;
            char[] newArray = Arrays.copyOfRange(array, offset, index);
            list1.add(newArray);
            if (index >= array.length) {
                list.add(list1);
                offset++;
                index = offset;
                generate(array, offset, index, new ArrayList<char[]>());
            } else {
                index++;
                generate(array, offset, index, list1);
            }
        }
    }