Java - 递归查找字符串(powerset)的所有子集

Question

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

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"。

Answer 1

具有 n 个元素的集合的子集数为 2ⁿ。例如，如果我们有字符串“abc”，我们将有 2ⁿ = 2³ = 8 个子集。

n位可以表示的状态数也是2ⁿ。我们可以证明枚举 n 位的所有可能状态与具有 n 个元素的集合的所有可能子集之间存在对应关系:

   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 处于 Activity 状态。如果我们执行 abc.charAt(0) + abc.charAt(2)，我们将得到子集 ac。

为了枚举 n 位的所有可能状态，我们从 0 开始，然后加一直到达到 2ⁿ - 1。在这个解决方案中，我们将从 2ⁿ 开始- 1 递减直到 0，所以我们不需要另一个参数来保持子集的数量，但效果是一样的:

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]