Algorithm to determine word supersets?

I play a word based tile game in which one tries to make words of increasingly long lengths where valid operations include adding one or more letters and rearranging what is already in place.

For example HIS → SHIV → HIVES → CHIVES → ANCHOVIES.

I wanted to create a program that outputs potential words you could make from the input word. Concisely, it finds all words that contain all the letters at least once from the input word in any order. There are online Scrabble solvers that have a similar but not identical functionality.

The first approach I had was to create a Trie (or DAFSA?) of the English language.
Then for each of the top level TrieNode entries of the data structure, invoke a function similar to this pseudocode

results : List<String> = []

fn Search(
  trieNode : TrieNode,
  prerequisites : MultiSet<Character>,
  letterStack : Stack<Character>):
    # setup context for this word
    letterStack.push(trieNode.letterValue)
    let removed : Character? = prerequisites.removeIfPresentOrNil(trieNode.letterValue)

    # add word if valid
    if trieNode.isWord and prerequisites.isEmpty():
       results.add(letterStack.join())
    
    # recurse on down-the-line possibilities
    for TrieNode n in trieNode.children:
       Search(n, prerequisites, wordStack)

    # teardown context before stack frame is popped
    letterStack.pop()
    prerequisites.addIfNotNil(removed)

Is this methodology, a depth first search across the entire English language, the best way to go about this problem? I don't want to reinvent the wheel if this is already a solved problem with an optimal solution.

Pseudo code

I am not sure I understood your pseudo code. Just in case, i will write what I have in mind using a tree for this problem (it might be what you wrote in your pseudo code):

1. for each word you create a key made of letters of word sorted (for instance "hello" gives "ehllo")
2. you create a dictionary: key --> list of words with this key
3. you create a tree using the keys
4. when a user gives a word, you get the key of the word, you move in the tree to corresponding node. result = All words in children nodes

Efficiency

With this algorithm, I think you can actually demonstrate that it is optimal in terms of time complexity, because:

• moving to the correct node in the tree takes O(1) (because the longest word in english has 29 characters, the tree is not deep)
• From this node, getting all words in all children nodes costs O(N_WORD_SOLUTION)
• So total time complexity is O(N_WORD_SOLUTION)

Knowing that you want to output a list that contains N_WORD_SOLUTION words, you can not have a better solution than O(N_WORD_SOLUTION)

Notes

• This algorithm is optimal without taking into account the time to build the tree. But the tree should be build once and then reuse for any call.
• I think it would be better to avoid recursive calls, you can write the same logic without recursion.