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

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"，这会导致重复。有什么好的解决方法吗？

在这里所指的幂集是指，如果字符串是 abc，则返回 "", "a", "b", "c", "ab", "ac", "bc", "abc"。

- Tim223

---

可能是重复的问题：Java - 使用递归从字符串创建所有子字符串 - ruhungry

代码没有正确处理空字符串的边缘情况。因此，如果您使用空字符串调用它，则会返回空字符串。 - Felix Leipold

我想现在我知道问题出在哪里了，但我不知道该如何解决。目前，我找到了 temp 的所有幂集，它们是“bcd”、“acd”、“abd”、“abc”，这会导致重复。有什么解决方法吗？ - Tim223

如果你考虑算法所遍历的树，有多种方法可以移除两个或更多字符（每个递归级别移除一个字符）。因此，当首先移除a然后移除b时，你会得到c；当首先移除b然后移除a时，你也会得到c。 - Felix Leipold

我看到了问题，只是不知道该如何以不同的方式解决它。这个问题有快速解决方法吗？还是我应该从头开始重新做？ - Tim223

可能是计算一组数字的所有子集的重复问题。 - David Eisenstat

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是活动的。如果我们执行abc.charAt(0) + abc.charAt(2)，我们得到子集ac。

为了枚举n位所有可能的状态，我们从0开始，每次加1，直到达到2的n次方-1。在这个解决方案中，我们将从2的n次方-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]

- Anderson Vieira

Answer 2

有一种方法可以不使用递归来实现，它依赖于位串和子集之间的简单对应关系。

假设你有一个由三个字符组成的字符串“abc”，那么，就像你注意到的那样，子集将会是“”、“c”、“b”、“bc”、“a”、“ac”、“ab”和“abc”。

如果你制作一个表格，写出每个字符在子集中是否存在(存在为1，不存在为0)，则可以看到一种模式:

    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

对于长度为n的唯一字符字符串，您将有2ⁿ个子集，并且可以通过简单地使一个for循环从i=0到i=2ⁿ-1，并仅包括那些对应于i中位为1的字符来生成它们所有。

我在此处编写了Java示例（链接）和C示例（链接）。

- tlehman

---

使用这种方法，您还可以轻松地迭代子集。最好的解决方案！谢谢你救了我的一天！ - hevi

最优雅且易于理解的方法。非常感谢。 - Harsh Gundecha

Answer 3

在设计递归算法时，我发现先考虑简单的边界情况很有帮助，即空字符串和只有一个字符的字符串。然后通常会将问题分解，并在字符串的其余部分/尾部进行递归调用。类似于这样：

    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;
}

- Felix Leipold

Answer 4

为了消除重复项，您只需要将它们全部添加到一个Set中，这可以通过某种助手轻松完成：

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;
}

另外，你的代码天生就已经处理了边界情况，你不需要担心这个。

- Jason Hu

---

在字符串“abc”上运行您的代码时，我遇到了StackOverflowError错误... - Nir Alfasi

@alfasin 因为这是递归。对于数据集过大的情况，它将无法工作。您可以尝试使用不需要堆栈的其他语言，或者使用技巧来实现它。 - Jason Hu

调试你的代码，set.addAll(_powerSet(tmp); 正在创建一个无限递归调用！ - Nir Alfasi

@alfasin 忘记了这个。它会循环，因为s.substring(i, s.length())，所以问题的规模没有减小。我把它改成了s.substring(i+1, s.length())。这应该可以解决问题。 - Jason Hu

Answer 5

你说得对，你有重复数据，因为每次创建 temp 时都没有添加另一个字符，所以当你递归调用时，会有不同的子集共享相同的字符并创建重复数据。例如，"abc" 将创建一个带有以下内容的 temp：["ab", "ac", "bc"]，每个子集将只使用一个字符进行递归调用，因此你将会得到每个 "a"、"b" 和 "c" 两次。

避免这种情况的一种方法（只需进行最小更改）是使用 Set 而不是列表 - 这将省略所有重复数据：

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;
}

现在的输出将会是：

bc
a
ab
b
ac
abc
c

一个不同的解决方案：

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);
}

输出

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

- Nir Alfasi

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);
            }
        }
    }

- Isuru Sameera