C++ || Simple || Brute Force Recursion with Memoization || 🔥🔥
Intuition\nWe check for each word given and if it is comprised entirely of at least two shorter words in the given array then we store it in our ans vector.\n\n
# Intuition\nWe check for each word given and if it is comprised entirely of at least two shorter words in the given array then we store it in our ans vector.\n\n# Approach\nIterate through the each word. If upto any particular index, it is present in given vector then call recursively for next indices. Cnt shows how much time recursive function is called (cnt>1 shows every word concatenates at least two words given in array).\n\n\n# Code\n```\nclass Solution {\n    unordered_set<string> st;\n    int dp[10000][30][31];\n    bool check(int idx, vector<string>& words, int i, int cnt)\n    {\n        if(idx==words[i].size())\n        {\n            if(cnt>1) return true;\n            return false;\n        }\n        if(dp[i][idx][cnt]!=-1) return dp[i][idx][cnt];\n        for(int k=idx; k<words[i].size(); k++)\n        {\n            string t=words[i].substr(idx, k-idx+1);\n            if(st.find(t) != st.end() && check(k+1, words, i, cnt+1)) \n            {\n                return dp[i][idx][cnt] = 1;\n            }\n        }\n        return dp[i][idx][cnt] = 0;\n    }\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) \n    {\n        int n=words.size();\n        vector<string> ans;\n        for(auto &w: words) st.insert(w);\n        memset(dp, -1, sizeof(dp));\n        for(int i=0; i<n; i++)\n        {\n            if(check(0, words, i, 0)) ans.push_back(words[i]);\n        }  \n        return ans;      \n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']