在字符串中生成字符組合並不完全，爲什麼？

Question

我試圖生成字符串中的所有字符組合。所以第一個參數是給出的字符串，第二個參數是字母數。所以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); 
     } 
    } 
}