C++ Basic recursion + memoization - Travelling salesman Problem approach:
Intuition\n Describe your first thoughts on how to solve this problem. \nIf we can consider the overlapping among the strings as weights . then we can translate
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf we can consider the overlapping among the strings as weights . then we can translate the problem as find the order of the strings with maximum sum weight or maximum overlapping. \ni.e travel all the nodes in maximum weight \n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(N^2 * 2^n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(N^2 * 2^n)$$\n# Code\n```\nclass Solution {\npublic:\n\n    string solve(int idx , int vis , vector<string>&a , vector<vector<int>> &w ,vector<vector<string>> &dp){\n        int  n = a.size();\n        if(vis == ((1<<n)-1))\n            return "";\n        if(!dp[idx][vis].empty())\n            return dp[idx][vis];\n\n        int mini = 1e9;\n        string minS,tmp;\n        for(int i=0;i<n;i++){\n            if((vis & (1<<i))==0){\n                tmp = a[i].substr(w[idx][i]) + solve(i, (vis | (1<<i)) , a,w,dp);\n                if(tmp.size()<mini){\n                    mini = tmp.size();\n                    minS=tmp;\n                }\n            }\n        }\n        return dp[idx][vis] = minS;\n    }\n    \n    string shortestSuperstring(vector<string>& a) {\n        int N = a.size();\n        vector<vector<string>> dp(N+1 , vector<string>((1<<N)+1,""));\n        vector<vector<int>> w(N,vector<int>(N,0));\n        //O(N^2 * W)\n        for(int i=0;i<N;i++){\n            for(int j=0;j<N;j++){\n                if(i==j)\n                    w[i][j]=a[i].size();\n                else{\n                    int k = min(a[i].size(),a[j].size());\n                    // max overlap value when taking i from end and j from start\n                    for(;k>=0;k--){\n                        if(a[i].substr(a[i].size()-k) == a[j].substr(0,k)){\n                            w[i][j]=k;\n                            break;\n                        }\n                    }\n                }\n            }\n        }\n        // for(vector<int> r : w){\n        //     for(int i : r) cout<<i<<" ";\n        //     cout<<endl;\n        // }\n        string minS,tmp;\n        int mini=1e9;\n        for(int idx =0 ;idx<N;idx++){\n            int vis = 0;\n            vis = vis | (1<<idx);\n            tmp = a[idx] + solve(idx,vis,a,w,dp);\n            if(tmp.size()<mini){\n                mini = tmp.size();\n                minS=tmp;\n            }\n        }\n        return minS;        \n    }\n};\n```
['C++']