java - 在Java中查找集合组合的递归算法

Question

我试图找到一些示例，说明如何在 Java 中查找给定集合(可能是字符串或整数数组)的所有组合。我遇到了这段代码(在 http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html 中找到。我在这里只复制了相关部分。):

// print all subsets of the characters in s
public static void comb1(String s) { comb1("", s); }

// print all subsets of the remaining elements, with given prefix 
private static void comb1(String prefix, String s) {
    if (s.length() > 0) {
        System.out.println(prefix + s.charAt(0));
        comb1(prefix + s.charAt(0), s.substring(1));
        comb1(prefix,               s.substring(1));
    }
}  

// read in N from command line, and print all subsets among N elements
public static void main(String[] args) {
   int N = Integer.parseInt(args[0]);
   String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
   String elements = alphabet.substring(0, N);

   // using first implementation
   comb1(elements);
   System.out.println();
}

但是，我真的不明白它是如何工作的。有人愿意解释一下吗？

Answer 1

创建给定集合的所有组合非常简单。你有 N 个元素，在每个组合中一个元素存在或不存在，所以你有 2^N 组合。该递归函数正是这样做的。它从该列表中选择每个元素并创建包含它的组合并创建不包含它的组合。注意:它不会打印出空组合。

如果仍然不清楚，创建一个简短的测试字符串(例如:3 个字符)，启动调试器并查看它是如何工作的。