Recursive backtracking to create permutations of given string

Question

I am currently working on a programming assignment where the user inputs a word

i.e. "that"

and the program should return all valid words that can be made from the given string

i.e. [that, hat, at]

The issue I am having is that the resulting words should be created using a recursive method that checks if the prefix is valid.

i.e. if the given word is "kevin" once the program tries the combination "kv" it should know that no words start with kv and try the next combination in order to save time.

Currently my code just creates ALL permutations which takes a relatively large amount of time when the input is larger than 8 letter.

protected static String wordCreator(String prefix, String letters) {
    int length = letters.length();

        //if each character has been used, return the current permutation of the letters
        if (length == 0) {
            return prefix;
        }
        //else recursively call on itself to permute possible combinations by incrementing the letters
        else {
            for (int i = 0; i < length; i++) {
                words.add(wordCreator(prefix + letters.charAt(i), letters.substring(0, i) + letters.substring(i+1, length)));
            }
        }
        return prefix;
    }

If anyone could help me figure this out I'd be much appreciated. I am also using an AVL tree to store the dictionary words for validation incase that is needed.