C++ O(N^2 * 2^N) Bitmask DP + DFS solution w/ explanation
The idea is that after selecting some words, we have to find the minimum length of the remaining superstring. For that we check all the remaining words. The sel
The idea is that after selecting some words, we have to find the minimum length of the remaining superstring. For that we check all the remaining words. The selected words are marked by the bitmask. After finding the minimum length, simply run an O(N^2) DFS for finding the answer.\n```\nint min(int a,int b)\n{\n    return a<b?a:b;\n}\nstring ret;\nint memo[4096][12];\nint overlap[12][12];\nvoid fun(vector<string>& words)\n{\n    for(int i=0;i<words.size();++i)\n        for(int j=0;j<words.size();++j)\n        {\n            if(i==j)\n                continue;\n            int count=0;\n            for(int start=0;start<words[i].size();++start)\n                if(words[i][start]==words[j][0])\n                    for(int k=start;k<words[i].length();++k)\n                        if(words[i][k]!=words[j][count])\n                        {\n                            count=0;\n                            break;\n                        }\n                        else\n                        {\n                            ++count;\n                            if(k==words[i].length()-1)\n                                goto breakp;\n                        }\nbreakp:     overlap[i][j]=count;\n        }\n}\nint dp(int mask,int pre,int allmask,vector<string>& words)\n{\n    if(mask==allmask)\n        return 0;\n    else if(memo[mask][pre]!=-1)\n        return memo[mask][pre];\n    else\n    {\n        int q=INT_MAX;\n        for(int i=0;i<words.size();++i)\n            if((mask&(1<<i))==0)\n                q=min(q,words[i].length()-(mask?overlap[pre][i]:0)+dp(mask|1<<i,i,allmask,words));\n        return memo[mask][pre]=q;\n    }\n}\nvoid dfs(int mask,int allmask,int pre,vector<string>& words)\n{\n    if(mask==allmask)\n        return;\n    else\n    {\n        for(int i=0;i<words.size();++i)\n            if(!mask)\n            {\n                if(memo[mask][pre]==words[i].length()+dp(1<<i,i,allmask,words))\n                {\n                    ret=words[i];\n                    dfs(1<<i,allmask,i,words);\n                    break;\n                }\n            }\n            else\n                if(memo[mask][pre]==words[i].length()-overlap[pre][i]+dp(mask|1<<i,i,allmask,words))\n                {\n                    ret+=words[i].substr(overlap[pre][i]);\n                    dfs(mask|1<<i,allmask,i,words);\n                    break;\n                }\n    }\n}\nstring shortestSuperstring(vector<string>& A) \n{\n    memset(memo,-1,sizeof(memo));\n    int n=A.size(),pre=0;\n    int allmask=(1<<n)-1;\n    memset(overlap,0,sizeof(overlap));\n    fun(A);        \n    dp(0,0,allmask,A);\n    dfs(0,allmask,0,A);\n    return ret;\n}\n```
['Dynamic Programming', 'Depth-First Search', 'C', 'Bitmask']