C++ Solutions, Backtrack, DP, or Trie.
First, I provide my working solution using unorederd_set. But I think a better solution should use Trie. Though it passed all test cases, I always get MLE. But 
First, I provide my working solution using unorederd_set. But I think a better solution should use Trie. Though it passed all test cases, I always get MLE. But the java solution using Trie can be accepted. Did anybody have any suggestions about this? I have already made some optimization on it, e.g., a word that can be concatenated by shorter words will not be inserted into the Trie. But I still get MLE.\n\nunordered_set solution  486 ms\n```\nvector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        vector<string> result;\n        if(words.empty()) return result; \n        auto mycomp = [&](const string& str1, const string& str2){return str1.size() < str2.size();};\n        sort(words.begin(), words.end(), mycomp);\n        unordered_set<string> mp;\n        for(auto& word: words) {\n            string path = "";\n            if(dfs(word, 0, path, 0, mp)) result.push_back(word); // We don't need to insert this word, because it can be concatenated from other words.\n            else mp.insert(word); \n        }\n        return result;\n    }\n    \nprivate:\n    bool dfs(string& word, int pos, string& path, int nb, unordered_set<string>& mp) {\n        if(pos == word.size()) {\n            if(mp.find(path) != mp.end() && nb > 0) return true;\n            else return false;\n        }\n        path.push_back(word[pos]);\n        if(mp.find(path) != mp.end()) {\n            string temp = "";\n            if(dfs(word, pos+1, temp, nb+1, mp)) return true;\n        }\n        if(dfs(word, pos+1, path, nb, mp)) return true;\n        else return false;\n    }\n```\n\nDP solution based on Word Break  739 ms\n```\nvector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        vector<string> result;\n        if(words.empty()) return result; \n        auto mycomp = [&](const string& str1, const string& str2){return str1.size() < str2.size();};\n        sort(words.begin(), words.end(), mycomp);\n        unordered_set<string> mp;\n        for(auto& word: words) {\n            string path = "";\n            if(wordBreak(word, mp)) result.push_back(word); // We don't need to insert this word, because it can be concatenated from other words.\n            else mp.insert(word); \n        }\n        return result;\n    }\n    \nprivate:\n    bool wordBreak(string& s, unordered_set<string>& wordDict) {\n        if(s.empty() || wordDict.empty()) return false;\n        vector<bool> dp(s.size()+1, false);\n        dp[0] = true;\n        for(int i = 1; i <= s.size(); i++) {\n            for(int k = i-1; k >= 0; k--) {\n                if(dp[k] && wordDict.find(s.substr(k, i-k)) != wordDict.end()) {\n                    dp[i] = true;\n                    break;\n                }\n            }\n        }\n        return dp[s.size()];\n    }\n```\n\nHere I provide my Trie-based solution, but it gets MLE.\n```\nclass Solution {\npublic:\n    struct TrieNode {\n        bool isWord;\n        unordered_map<char, TrieNode*> children;\n        TrieNode(): isWord(false) {};\n    };\n\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        vector<string> result;\n        if(words.empty()) return result; \n        auto mycomp = [&](const string& str1, const string& str2){return str1.size() < str2.size();};\n        sort(words.begin(), words.end(), mycomp);\n        \n        root = new TrieNode();\n        for(auto& word: words) {\n            if(dfs(word, 0, root, 0)) result.push_back(word);\n            else insert(word);\n        }\n        return result;\n    }\n    \nprivate:\n    TrieNode* root;\n    \n    void insert(string& word) {\n        auto run = root;\n        for(char c: word) {\n            if(run->children.find(c) == run->children.end()) {\n                TrieNode* newnode = new TrieNode();\n                run->children[c] = newnode;\n            }\n            run = run->children[c];\n        }\n        run->isWord = true;\n    }\n    \n    bool dfs(string& word, int pos, TrieNode* node, int nb) {\n        if(pos == word.size()) {\n            if(node->isWord && nb > 0) return true;\n            else return false;\n        }\n        \n        if(node->children.find(word[pos]) == node->children.end()) return false;\n        auto next = node->children[word[pos]];\n        if(next->isWord) {\n            if(dfs(word, pos+1, root, nb+1)) return true;\n        }\n        if(dfs(word, pos+1, next, nb)) return true;\n        else return false;\n    }\n};\n```
[]