Accepted (192ms) C++ solution using DP and Trie
Following is pretty straight-forward, kind-of brute-force approach that result to TLE upon submission. Almost all the solution-posts follow this approach and re
Following is pretty straight-forward, kind-of brute-force approach that result to TLE upon submission. Almost all the solution-posts follow this approach and result to TLE with newly added test-cases.  \n```\nclass Solution {\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        sort(words.begin(), words.end(), [](string& w1, string& w2){\n            return (w1.length() <= w2.length());\n        });\n        \n        vector<string> ret;\n        unordered_set<string> m;\n        \n        for(string w : words) {\n            vector<bool> dp(w.length()+1, false);\n            dp[0] = true;\n            for(int i = 0; i < w.length(); i++) {\n                for(int j = i; j >= 0; j--) {\n                    string s = w.substr(j, i-j+1); // O(length) operation\n                    if(dp[j] && m.find(s) != m.end()) {\n                        dp[i+1] = true;\n                        break;\n                    }\n                }\n            }\n            \n            if(dp[w.length()])\n                ret.push_back(w);\n            \n            m.insert(w);\n        }\n        \n        return ret;\n    }\n};\n```\n\nTime complexity : *O(N * L^3)*, where N = number of words and L = length of word.  \n\nWhile applying DP for each of the word, we are using `substr` to calculate the suffix and then searching it on `map`. We can use a `trie` instead to check if current suffix is a valid smaller word. That will bring down the complexity from `O(length)` to `O(1)`. \n\nSo, following snippet\n```\nfor(int j = i; j >= 0; j--) {\n    string s = w.substr(j, i-j+1); // O(length) operation\n    if(dp[j] && m.find(s) != m.end()) {\n        dp[i+1] = true;\n        break;\n    }\n}\n``` \ncan be replaced with (provided that the word has been inserted into trie in reverse order)\n```\ntrie* node = root;\nfor(int j = i; j >= 0; j--) {\n    if(node->arr[w[j]-\'a\'] == NULL)\n        break;\n    node = node->arr[w[j]-\'a\'];\n    if(dp[j] && node->end) {\n        dp[i+1] = true;\n        break;\n    }\n}\n```\n\nHere is the final accepted version,\n```\nclass Solution {\n    struct trie{\n\t    struct trie* arr[26];\n\t    bool end = false;\n\t    trie() {\n\t\t    memset(arr,0,sizeof(arr));\n\t\t    end = false;\n\t    }\n    };\n\n    trie* root;\n\n    void insert(string s){\n        trie* node = root;\n        /* \n         * inserting the string in reverse order as we will search from the\n         * end (i.e. suffix) of the word while using DP.\n         */\n        for(int i = s.length()-1; i >= 0; i--) {\n            char ch = s[i];\n            if(!node->arr[ch-\'a\']) {\n                node->arr[ch-\'a\'] = new trie();\n            }\n            node = node->arr[ch-\'a\'];\n        }\n        node->end = true;\n    }\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        /* \n         * every word can be generated by concatinating smaller words only,\n         * so smaller words will be processed and inserted into trie first \n         */\n        sort(words.begin(), words.end(), [](const string& w1, const string& w2) {\n            return (w1.size() < w2.size());\n        });\n        \n        vector<string> ret;\n        root = new trie();\n        \n        for(string w : words) {\n            if(w.length() == 0)\n                continue;\n            \n            vector<bool> dp(w.length()+1, false);\n            dp[0] = true;\n            for(int i = 0; i < w.length(); i++) {\n                trie* node = root;\n                for(int j = i; j >= 0; j--) {\n                    /* \n                     * instead of keeping the smaller words into a map and \n                     * searching in the map after doing substr() which is O(n)\n                     * operation, trie is being used here to achieve constant \n                     * time search operation of current suffix\n                     */ \n                    if(node->arr[w[j]-\'a\'] == NULL)\n                        break;\n                    node = node->arr[w[j]-\'a\'];\n                    if(dp[j] && node->end) {\n                        dp[i+1] = true;\n                        break;\n                    }\n                }\n            }\n            \n            if(dp[w.length()])\n                ret.push_back(w);\n            \n            insert(w);\n        }\n        \n        return ret;\n    }\n};\n```\n\nTime complexity : *O(N * L^2)*, where N = number of words and L = length of word.
['Dynamic Programming', 'Trie', 'C']