打印由n个字符组成的长度为k的所有可能的字符串，而不需要重复结构

Question

打印由n个字符组成的长度为k的所有可能的字符串是一个常见的问题，并且已经有了解决方案。

不过，我希望知道

null

输出：

aaa
aab
aba
abb
abc

对于复杂度要求：它不应大于O(n^k)。

Answer 1

您可以调整现有的解决方案。您需要添加的限制是，只有在列表中该字符之前的所有其他字符至少出现过一次之后，该字符才能出现在字符串中。这起作用是因为对于具有相同重复结构的每组字符串，只有一个字符的首次出现是按照它们在列表中出现的顺序，所以这就是您输出的一个。您可以使用一个额外的参数来强制执行此限制：

static void printAllKLengthRec(char[] set, 
                            String prefix, 
                            int n, int k, int validCount)
{

    // Base case: k is 0, print prefix
    if (k == 0) 
    {
        System.out.println(prefix);
        return;
    }

    // One by one add all valid characters and recursively call for k equals to k-1
    for (int i = 0; i < validCount; ++i)
    {

        // Next character of input added
        String newPrefix = prefix + set[i]; 

        // increment the valid count if all characters up till then have already
        // appeared and there are characters that have not yet appeared
        // (i.e. validCount < n)
        int newValidCount = (i == (validCount - 1)) && (validCount < n) ?
            validCount + 1 :
            validCount;

        // k is decreased, because we have added a new character
        printAllKLengthRec(set, newPrefix, 
                                n, k - 1, newValidCount); 
    }
}

例如，如果您的集合为{'a','b','c','d'}并且validCount为3，则表示a和b已经出现，因此可以将a或b或c附加到字符串中。如果您追加了c，那么在递归调用函数之前增加值，因为现在a和b和c至少出现过一次，所以现在可以追加d了。如果附加a或b，则值将保持不变。

对于排列中的第一个字符,只能显示列表中的第一个字符：

static void printAllKLength(char[] set, int k)
{
    int n = set.length; 
    printAllKLengthRec(set, "", n, k, 1);
}