Написание последовательности программ на Java с использованием рекурсии

Question

Передо мной была поставлена ​​задача найти все подпоследовательности для строки.

Например, если строка "bat", подпоследовательность возвращает [, b, ba, at, bt, t]

Обратите внимание, что в нем нет всех перестановок строки, поскольку она должна идти по порядку. Первая строка является пустой строкой, и это, очевидно, требуется инструкциями.

Другим примером является строка "brat". Ожидаемый результат для этого будет [, a, at, b, ba, bat, br, бюстгальтер, brat, brt, bt, r, ra, rat, rt, t]

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

Это то, что я имею до сих пор:

import java.util.ArrayList;
public class Sequences {
   public static ArrayList<String> sequences(String s) {
      ArrayList<String> list = new ArrayList<String>();      
      return subsequences(s, list);
   }
   public static ArrayList<String> sequences(String s, ArrayList<String> list) {
       list.add("");
       if (s.length() == 0) 
           list.add(s);
       else {
           list.add(s);
           String temp = s.substring(0,1);
           String next = s.substring(1, s.length());
           list.add(temp);
           sequences(next);
       }
       return list;
   }
}

Я также написал тестер очень быстро, чтобы я мог проверить проблему, поскольку тестер нам не предоставили:

  public class tester {
    public static void main(String[] args) {
        System.out.println(Sequences.sequences("at"));
    }
}

Вывод, который я получаю, это [, a], когда я должен был получить [, a, at, t]

Любая помощь будет приветствоваться!

Answer 1

Ваш алгоритм неверен.Одним из решений проблемы является следующее:

На каждом шаге рекурсии откладывайте в сторону первый символ и вычисляйте все подпоследовательности остальных.Затем добавьте все вычисленные подпоследовательности дважды: один раз без первого символа и другой раз с добавлением символа.

public class Sequences {

    public static ArrayList<String> sequences(String s) {
        ArrayList<String> list = new ArrayList<String>();
        if (s.length() == 0) {
            list.add("");
            return list;
        }
        String firstChar = s.substring(0, 1);
        String theRest = s.substring(1, s.length());
        ArrayList<String> siffixSequence = sequences(theRest);
        list.addAll(siffixSequence);
        for (String string : siffixSequence) {
            list.add(firstChar + string);
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(Sequences.sequences("brat"));
        // prints [, t, a, at, r, rt, ra, rat, b, bt, ba, bat, br, brt, bra, brat]
    }

}

Answer 2

Вы не делаете что-либо с sequences(next) в рекурсии.Если вы сможете выяснить, что с этим делать, вы будете настроены.