给定一串字母和一个数字k,编写一个函数来打印这些字母的长度k的所有组合。
  
  该字符串不包含重复的字母。
  
  输入:{ 'a', 'b', 'd', 's', 'e' }
  
  预期输出:abd, abs, abe, ads, ade, bds, bde, bse, dse


我正在使用递归。

基本情况是int k为0时返回前缀。

如果不满足基本要求,请逐步添加字符数组中的所有字符,然后递归调用k = k - 1

// Recursive method used to print all possible strings of length k, given a set of characters.
private static void printAllCombinations(char[] alphabet, String prefix, int n, int k) {
    // Base case: k is 0,
    // print prefix.
    if (k == 0) {
        System.out.print(prefix + " ");
        return;
    }

    // One by one add all characters
    // from set and recursively
    // call for k equals to k - 1.
    for (int i = 0; i < n; i++) {
        // Next character of input added.
        String newPrefix = prefix + alphabet[i];

        // k is decreased, because
        // we have added a new character.
        printAllCombinations(alphabet, newPrefix, n, k - 1);
    }
}


实际输出:aaa aab aad aas aae aba abb abd abs abe ada adb add ads ade asa asb asd ass ase aea aeb aed aes aee baa bab bad bas bae bba bbb bbd bbs bbe bda bdb bdd bds bde bsa bsb bsd bss bse bea beb bed bes bee daa dab dad das dae dba dbb dbd dbs dbe dda ddb ddd dds dde dsa dsb dsd dss dse dea deb ded des dee saa sab sad sas sae sba sbb sbd sbs sbe sda sdb sdd sds sde ssa ssb ssd sss sse sea seb sed ses see eaa eab ead eas eae eba ebb ebd ebs ebe eda edb edd eds ede esa esb esd ess ese eea eeb eed ees eee

我可以做些什么来获得所需的输出?

我知道我的功能printAllCombinations实际上正在按预期方式工作。我只是不明白如何实现所需的输出。

最佳答案

您可以使用n跟踪数组alphabets中的当前位置。

public static void printAllCombinations(char[] alphabet, int k) {
    printAllCombinations(alphabet, "", 0, k);
}
private static void printAllCombinations(char[] alphabet, String prefix, int n, int k) {
    if (k == 0) { //base case unchanged
        System.out.print(prefix + " ");
        return;
    }
    for (int i = n; i < alphabet.length; i++) { //loop only from n to end of array
        String newPrefix = prefix + alphabet[i];

        printAllCombinations(alphabet, newPrefix, i + 1, k - 1);
    }
}


输出:abd abs abe ads ade ase bds bde bse dse

如果要在除第一个元素之外的每个元素前都使用逗号,则可以将基本情况更改为:

if (k == 0) {
    if (n > prefix.length()) {
        System.out.print(", ");
    }
    System.out.print(prefix);
    return;
}


将输出:abd, abs, abe, ads, ade, ase, bds, bde, bse, dse

10-06 07:27