Вывести все подпоследовательности строки с помощью рекурсии с возвратом в Java

Question

Я знаю, что это вопрос, который часто задавался здесь, и есть много примеров в Интернете, но я не нашел такой, который соответствует моему вопросу.

---

Мне нужно написать код, который получит строку и напечатает все различные подпоследовательности в порядке их появления в слове. Решение должно иметь только рекурсивный метод (методы), без циклов вообще. (должно основываться на рекурсии с возвратом назад и только массивах или подстроках) "," 02 "," 012 "

сначала я собирался что-то вроде этого:

public static void printSubs(String s) {
    printSubsSol(s, "");
}

private static void printSubsSol(String s, String temp) {
    if (s.length()==0) {
        System.out.print(temp+" ");
        return;
    }
    printSubsSol(s.substring(1), temp);
    printSubsSol(s.substring(1),temp+s.charAt(0));
}

Отпечатки: 2 1 12 0 02 01 012

Я не смог напечатать все подпоследовательности в правильном порядке, поэтому теперь я попробовал другой подход с использованием массива char, который с моим чуть более успешным задом, я не еще нет

public class Ex9Q2V4 {
public static void printSubs(String s) {
    char[] tempArr = new char[s.length() - 1];
    printSubsSol(s, 0, 0, tempArr, 1);
    System.out.println('"' + s + '"');
}

private static boolean isSafe(int arrayIndex, int currentIndex, int howMuchToPrint, int length) {
    return (arrayIndex < howMuchToPrint && arrayIndex <= currentIndex && currentIndex < length);
}

private static void printSubsSol(String s, int arrayIndex, int currentIndex, char[] charArr, int howMuchToPrint) {
    if (howMuchToPrint == s.length()) {
        return;
    }
    charArr[arrayIndex] = s.charAt(currentIndex);
    if (arrayIndex == howMuchToPrint - 1) {
        System.out.print("\"");
        printArray(charArr, howMuchToPrint);
        System.out.print("\"" + ", ");
    }
    if (isSafe(arrayIndex + 1, currentIndex + 1, howMuchToPrint, s.length())) {
        printSubsSol(s, arrayIndex + 1, currentIndex + 1, charArr, howMuchToPrint);

    }
    else if (isSafe(arrayIndex, currentIndex + 1, howMuchToPrint, s.length())) {
        printSubsSol(s, arrayIndex, currentIndex + 1, charArr, howMuchToPrint);

    }
    else printSubsSol(s, 0, 0, charArr, howMuchToPrint + 1);
}

// A method that prints the array
private static void printArray(char arr[], int n) {
    if (n != 0) {
        printArray(arr, n - 1);
        System.out.print(arr[n - 1]);
    }
}

}

Печать: «0», «1», «2», «01», «02», «12», «012»

Если возможно, я буду рад видеть решение обоими способами.

Answer 1

Я нашел алгоритм в C онлайн и преобразовал его в Java и использовал Strings. Вы можете увидеть статью здесь

Я должен был сохранить значения в TreeSet, чтобы получить желаемый заказ.

Вот как это назвать.

        String str = "0123";

        Set<String> set = new TreeSet<>(Comparator
                .comparing(String::length)
                .thenComparing(Comparator.naturalOrder()));

        subseq(str, 0, "", set);

        set.forEach(System.out::println);

А вот и модифицированный алгоритм.

    static void subseq(String arr, int index, String subarr,
            Set<String> set) {
        if (index == arr.length()) {
            int l = subarr.length();
            if (l != 0) {
                set.add(subarr.substring(0, l));
            }
        } else {
            subseq(arr, index + 1, subarr, set);
            subarr = subarr
                    + arr.substring(index, index + 1);
            subseq(arr, index + 1, subarr, set);
        }
        return;
    }

Answer 2

Давайте посмотрим с al oop

for (int i = 1; i <= s.length(); i++) {
     for (int j = 0; j + i <= s.length(); j++) {
          System.out.print(s.substring(j, j + i) + " ");
     }
}

Вы идете по правильному пути со своей второй идеей, вам нужен индекс и длина, но она кажется слишком сложной.

static void print(String s, int start, int length) {
    System.out.print(s.substring(start, start + length) + " ");
    if (start + length < s.length())
        print(s, start + 1, length);
    else if (length < s.length())
        print(s, 0, length + 1);
}

Сначала мы печатаем подстроку.

Условие if является вложенным l oop, если начальный индекс + длина для печати по-прежнему ниже длины строки, мы просто увеличиваем начальный индекс

Другая часть - это первая l oop, когда вы достигли конца входной строки и больше не можете подстроку, вы устанавливаете начальный индекс обратно на 0 и увеличиваете длину. Если длина равна длине ввода, рекурсия останавливается

Конечно, сначала вы должны проверить, не является ли вход пустым