Java - 递归查找字符串（幂集）的所有子集

因此，我需要递归地查找给定字符串的所有子集。到目前为止我所拥有的是：

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;

我想我现在知道问题是什么，但我不知道如何解决。目前，我找到了temp的所有幂集，分别是“bcd”、“acd”、“abd”、“abc”，这会导致重复。有想法该怎么解决这个吗？

通过 powerset，我的意思是如果字符串是 abc，它将返回“”、“a”、“b”、“c”、“ab”、“ac”、“bc”、“abc”。

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

例如，如果我们考虑第 5 行，则位 2 和 0 处于活动状态。如果我们这样做abc.charAt(0) + abc.charAt(2)我们得到子集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;
}

然后你只需要调用它：

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

并获取所有 8 个子集：

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