Вы можете адаптировать существующее решение. Ограничение, которое вам нужно добавить, заключается в том, что символ может появляться в строке только после того, как все остальные символы перед тем, как он появится в списке, появятся хотя бы один раз. Это работает, потому что для каждого набора строк с одинаковой повторяющейся структурой, есть только одна, где первое появление каждого символа находится в порядке, в котором они появляются в списке, так что это та, которую вы выводите. Вы можете применить это ограничение с помощью дополнительного параметра:
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);
}