在字符串中生成字符组合并不完全有效，为什么？

我正在尝试生成字符串中所有字符的组合。 所以第一个参数是给定的字符串，第二个参数是字母数。 所以combinations("ab",2)应该给我aa, ab, ba, bb和combinations("abc",2)应该给我aa, ab, ac, ba, bb, bc, ca, cb, cc等。

在第一种情况下，我当前的代码给了我aa, ab, bb （所以它跳过ba ）。 这是我的代码：

  public static void combinations(String s, int n) { combinations(s,"",n); } public static void combinations(String s, String prfx, int n) { if(n == 0) { System.out.println(prfx); } else { for(int i = 0; i < s.length(); i++) { combinations(s.substring(i), prfx + s.charAt(i), n-1); } } } 

我究竟做错了什么？ 如果你不只是给我正确答案，我会很感激，但也给我一些解释，以便我可以从中学习，因为我不太擅长递归。 谢谢。

Answer 1

问题的根源在于：

  combinations(s.substring(i), prfx + s.charAt(i), n-1); ^^^^^^^^^^^^^^ 

您希望遍历字符串中的字符并依次使用每个字符作为前缀，然后进行递归调用以构建字符串其余部分的组合。 但是，如果只将原始字符串的子字符串传入递归调用，则不会生成所有可能的排列。 在上面的例子中，正如你所观察到的，它跳过了“ba”，因为当循环到达字符串“ab”的第二个字符时（当循环计数器i为1时），这个递归调用是： combinations("b", "" + "b", 1) 。 哪个只能生成“bb”，而不是“ba”。 如果它是combinations("ab", "" + "b", 1) ，你将得到两个预期的组合“ba”和“bb”。

所以你需要将整个字符串传递给每个递归调用：

  combinations(s, prfx + s.charAt(i), n-1); 

Answer 2

这有效：

 public static void combinations(String s, int n) { combinations(s, "", n); } public static void combinations(String s, String prfx, int n) { if (n == 0) { System.out.println(prfx); } else { for (int i = 0; i < s.length(); i++) { combinations(s, prfx + s.charAt(i), n - 1); } } }