Print all sub-sequences of a string using backtracking recursion in Java

Question

I know that's a question that has been asked here a lot, and there is plenty of examples online, but I didn't found one that matches my question.

---

I need to write a code that will receive a string and will print all the different sub-sequences in the order they appear in the word. The solution should have recursive method(s) only, with no loops at all. (should be based on backtracking recursion and arrays or substrings only, apparently)

For example '012' should print: "0", "1", "2", "01", "12", "02", "012"

at first i was going for something like this:

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));
}

Prints: 2 1 12 0 02 01 012

I wasn't able to print all the sub-sequences in the right order, so now I tried a different approach using a char array, which with I had a bit more success bum I'm not there yet

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]);
    }
}

}

Prints: "0", "1", "2", "01", "02", "12", "012"

If possible, I will love to see the solution in both ways.

Answer 1

I found an algorithm in C online and converted it to Java and to use Strings. You can see the article here

I had to store the values in a TreeSet to get the desired order.

Here is how to call it.

        String str = "0123";

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

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

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

And here is the modified algorithm.

    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;
    }