Finding all possible combinations within a String using permutation

Question

I currently have two methods which uses recursion to give me all of the possible combinations of a given String, I got to this with the help of this answer. So if I entered the String and it returns these combinations:

and
adn
dan
dna
nad
nda

However I want it to return all possible combinations of the rest of even one/two letters in that string like so:

a
n
d
an
ad 
na
nd
etc...

Something like this answer but in java

That answer also mentioned and linked Powersets which showed all possible subsets of a,b,c:

As you can see it doesn't do the combinations back to front such as

c,b,a
c,a,b
c,a
....

Here's the current code I have where I would like to implement this:

public void permutation(String str) {

  permutation("", str);
}

private void permutation(String prefix, String str) {

    int n = str.length();
    if (n == 0) myList.add(prefix);
    else {
        for (int i = 0; i < n; i++)

            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));

    }
}

Answer 1

    if (n == 0) myList.add(prefix);

This statement you've provided only adds it if you've permuted all characters available in str.

If you remove the if (n == 0) it'll add all the prefixes from a to an to and, so you would instead use:

private void permutation(String prefix, String str) {
    int n = str.length();
    myList.add(prefix);
    if(n > 0) {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));

    }

You'll obviously get a bunch of duplicates and possibly an empty string as a result of the recursion, but there is a Collection you can use that doesn't allow duplicates, or you can check if it is a duplicate before adding. I'll leave the optimization up to you.