How to get all dictionary words from a list of letters?

You can keep an auxiliary data structure and add a special symbol to mark an end-of-line:

#include <algorithm>
#include <string>
#include <set>
#include <list>
#include <iostream>
 
int main()
{
    std::list<int> l = {-1, 0 ,1, 2, 3, 4};
    std::string s = "fairy";
    std::set<std::string> words;
    do {
        std::string temp = "";
        for (auto e : l)
            if (e != -1) temp += s[e];
            else break;
        words.insert(temp);
    } while(std::next_permutation(l.begin(), l.end()));
}

Here the special symbol is -1

Okay, you have to ask yourself a question. Can you reuse letters? For instance, if you're given the word friend, is fee legal? Friend has 1 e and fee has 2. That's an important but minor detail.

Algorithm 1: Brute Force

You can iterate over your entire list of possible words and write a method "does this word consist only of letters in this other word"? If so, add it to your final list.

That algorithm changes very slightly based on your answer to the first question, but it's not hard to write.

Algorithm 2: Recursive Approach

Create a method addWords().

/**
 * letters is the list of letters you're allowed to use
 * word may not be empty
 */
void addWords(string letters, string word) {
    size_t length = word.length();

    for (int index = 0; index < length; ++index) {
         string newWord = word + letters[index];
         string remainingLetters = letters.substr(0, index) + letters(index + 1);
         // if newword is in your dictionary, add it to the output
         ...
         addWords(remainingLetters, newWord);
    }
}

Let's look how this works with addWords("fairy", "") --

First loop: add f to the empty string and check if f is a word. Then recurse with addWords("airy", f"). We'll look at recursion shortly.

Second loop: add a to the empty string and check if a is a word. It is, so we'll add it to the output and recurse with addWords("firy", "a").

Repeat, checking each one-letter word (5 times total).

Now, let's look at one level of recursion -- addWords("airy", "f"). Now, we're going to try in order fa, fi, etc. Then we'll recurse again with something like addWords("iry", "fa") (etc).

From recursing the second loop, we would try words beginning with a instead of f. So we would end up testing af, ai, etc.

This works if the answer to your first question is "no, we don't reuse letters". This method does NOT work if the answer is yes.

You can check every prefix (or suffix, you need only be consistent) of each permutation. This will consider some substrings multiple times, but it's a simple change.

std::unordered_set<std::string> permutations;

// Finds every permutation (non-duplicate arrangement of letters)
std::sort(letters.begin(), letters.end());
do {
    std::string_view view = letters;
    for (auto i = 1; i < view.size(); ++i) {
        auto prefix = view.substr(0, i);
        // check if prefix is dictionary word
        permutations.insert(prefix);
    }
} while (std::next_permutation(letters.begin(), letters.end()));

Algorithmically, you can use something like a counter to generate all subsets of your word, and then find all the permutations:

For example:

00000 ---> null
00001 ---> y
00010 ---> r
00011 ---> ry
00100 ---> i
00101 ---> iy
...
11110 ---> Fair
11111 ---> Fairy

Note: Now, do your permutation function for each word to generate other orders of the chars. See here for the permutation.

For implementing the counter, use something like a boolean array, and change the lowest bit, and update others if it needs. In each level, choose those "chars" that their indices are true in your boolean array.

Trie might be an appropriate structure to store the word.

I suggest also to use sorted anagram as "key" instead of the word directly:

class Node
{
public:
    std::map<char, Node> children; // Might be an array<std::unique_ptr<Node>, 26>

    std::set<std::string> data; // List of word valid with anagram
    // Traditionally, Trie would use instead ` bool endOfWord = false;`

    Node() = default;

    const Node* get(char c) const
    {
        auto it = children.find(c);

        if (it == children.end()) {
            return nullptr;   
        }
        return &it->second;
    }
};

class Trie
{
    Node root;
public:
 
    void add(const std::string& word)
    {
        std::string sorted = word;
        std::sort(sorted.begin(), sorted.end());
        Node* node = &root;
        for (const char c : sorted) {
            node = &node->children[c];
        }
        node->data.insert(word);
    }
// ...
};

Then to print all anagrams you might do:

void print_valid_words(std::string letters) const
{
    std::sort(letters.begin(), letters.end());
    print_valid_words(&root, letters);
}
    
private:

void print_valid_words(const Node* current, std::string_view letters) const
{
    if (current == nullptr) return;

    for (auto word : current->data) {
        std::cout << word << std::endl;   
    }
    for (std::size_t i = 0; i < letters.size(); ++i)
    {
        if (i == 0 || letters[i] != letters[i - 1]) {
            print_valid_words(current->get(letters[i]), letters.substr(i + 1));
        }
    }
}

Demo