使用Java中的回溯递归打印字符串的所有子序列

Question

我知道这个问题在这里已经问了很多，在线上有很多例子，但是我没有找到与我的问题相符的例子。

---

我需要编写一个代码，该代码将接收一个字符串，并按照它们在单词中出现的顺序打印所有不同的子序列。该解决方案应仅具有递归方法，完全没有循环。

例如，“ 012”应打印：“ 0”，“ 1”，“ 2”，“ 01”，“ 12”，“ 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数组的另一种方法，但是这种方式我无法打印所有子序列（我成功完成了打印除“ 12”或“ 02”以外的所有内容，这取决于我尝试使用的代码）。

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 void printSubsSol(String s, int arrayIndex, int currentIndex, char[] charArr, int howMuchToPrint) {
    if (howMuchToPrint == s.length()) {
        return;
    }
    if (currentIndex < s.length()) {
        charArr[arrayIndex] = s.charAt(currentIndex);
        if (arrayIndex == howMuchToPrint - 1) {
            System.out.print("\"");
            printArray(charArr, howMuchToPrint);
            System.out.print("\"" + ", ");
            printSubsSol(s, arrayIndex, currentIndex+1, charArr, howMuchToPrint);
        } else
            printSubsSol(s, arrayIndex+1, 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”，“ 012”]

我感觉我在鳕鱼数组中缺少一个'if'语句，但是我很想找出两者中的解决方案（如果可能的话）。

Answer 1

让我们一起循环看

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条件是嵌套循环，如果起始索引+要打印的长度仍小于字符串的长度，我们只需增加起始索引

else部分是第一个循环，当您到达输入字符串的末尾并且无法再子字符串时，可以将起始索引设置回0并增加长度。如果长度等于输入的长度，则递归停止]

当然应该首先检查输入是否为空

Answer 2

我认为这就是您想要的。您将其称为如下：

subseq(str, 0, 1, 1);  // str, s, e, i

1. s是要打印的字符串的开头。
2. e是字符串的结尾。
3. i只需为下一个递归调用增加itself和es重置为0。

查看此内容的最佳方法是放入一些打印语句并查看数字。

我想出来的方法是使用铅笔和纸来查看我想要的子字符串的索引。然后，我使用嵌套循环来完成它，然后将逻辑转移到递归解决方案。

也许有更好的递归方法，但这是我想出的。

    public static void subseq(String str, int s, int e,
            int i) {
        System.out.println(str.substring(s, e));
        if (e < str.length()) {
            subseq(str, s + 1, e + 1, i);
        } else if (s > 0) {
            subseq(str, 0, i + 1, i + 1);
        }
    }

注意，通常子序列是指不同的构建体。这涉及的是子字符串。查看this以获得更多信息。