C++ Recursive Dp + Path Finding ~20 ms
I try to maximise the overlap length in the salesman\'s total path.\n\n#define se second\n#define fi first\n#define dbg(x) cout<<#x<<" = "<<(x)<<endl;\n#define 
I try to maximise the overlap length in the salesman\'s total path.\n```\n#define se second\n#define fi first\n#define dbg(x) cout<<#x<<" = "<<(x)<<endl;\n#define dbg1(x,y) cout<<#x<<" = "<<(x)<<" | "<<#y<<" = "<<(y)<<endl;\ntypedef pair<int,int> ii;\ntypedef pair<int,ii> iii;\ntypedef vector<int> vi;\ntypedef vector<vi> iv;\nint n;\nint mx=-1;\niv g;\nint dp[14][((1<<14))];\n\nint rec(int idx,int mask){\n    if(mask==((1<<n)-1)){\n        return 0;\n    }\n    if(dp[idx][mask]!=-1) return dp[idx][mask];\n    for(int i=0;i<n;i++){\n        if(((1<<i)&mask)==0){\n            int temp=(mask|(1<<i));\n            dp[idx][mask]=max( dp[idx][mask] , g[idx][i]+rec(i,temp) );\n        }\n    }\n    return dp[idx][mask];\n}\n\nstring path(int x,int rem,int mask,vector<string> &A){\n    string out=A[x];\n    if(mask==((1<<n)-1)){\n        return out;\n    }\n    for(int i=0;i<n;i++){\n        if(((1<<i)&mask)==0){\n            if(g[x][i]+rec(i,(mask|(1<<i)))==rem){\n                string t=out;\n                string y=path(i,rem-g[x][i],(mask|(1<<i)),A);           \n                return out+y.substr(g[x][i]);\n            }\n        }\n    }\n}\n\n\n\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& A) {\n        int tot=0;\n        A.insert(A.begin(),"");\n        n=A.size();\n        g.clear();\n        g.resize(n,vi(n));\n        mx=0;\n        for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if(i!=j){\n            for(int k = min(A[i].size(), A[j].size()); k>0; --k)\n                if(A[i].substr(A[i].size()-k)==A[j].substr(0,k)){\n                    g[i][j] = k; \n                    break;\n                }\n        }\n        \n        memset(dp,-1,sizeof(dp));\n        int rem=rec(0,1);\n        string x=path(0,rem,1,A);\n        return x;\n    }\n};\n```\n
[]