C++ Bitmask DP: maintain choice made at each step of the recursion.
\n# Code\ncpp []\nint sufPref[12][12];\nint dp[12][1<<12];\nint choice[12][1<<12];\n\nclass Solution {\n    private:\n\n    int n;\n        \n    // length of t
\n# Code\n```cpp []\nint sufPref[12][12];\nint dp[12][1<<12];\nint choice[12][1<<12];\n\nclass Solution {\n    private:\n\n    int n;\n        \n    // length of the permutations\n    int f(int last, int mask, vector<string> &words) {\n        // if all strings added, no extra length\n        if (mask == (1<<n) - 1) return 0;\n        // if already computed, return\n        if (dp[last][mask] != INT_MAX) return dp[last][mask];\n\n        // compute the result\n        for (int i = 0; i < n; i++) {\n            if (mask & (1<<i)) continue;\n            int newLen = f(i, mask | (1<<i), words) - sufPref[last][i] + words[i].size();\n            if (newLen < dp[last][mask]) {\n                dp[last][mask] = newLen;\n                choice[last][mask] = i;\n            }\n        }\n\n        return dp[last][mask];\n\n    }\n\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        n = words.size();\n        fill_n(&dp[0][0], 12 * (1<<12), INT_MAX);\n        fill_n(&choice[0][0], 12 * (1<<12), -1);\n\n        // What is the largest suffix of i that is a prefix of j?\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                int l1 = words[i].size(), l2 = words[j].size();\n                int len = min(l1, l2);\n\n                sufPref[i][j] = 0;\n\n                for(int k = 1; k <= len; k++) {\n                    int x = l1 - k, y = 0;\n                    while (y < k and words[i][x] == words[j][y]) {x++; y++;}\n                    if (y == k) sufPref[i][j] = k;\n                }\n            }\n        }\n\n        // check the prefix matches\n        // for (int i = 0; i < n; i++) {\n        //     for (int j = 0; j < n; j++) cout << sufPref[i][j] << " ";\n        //     cout << endl;\n        // }\n\n        int minlen = 10000, minword = 0;\n        for (int i = 0; i < n; i++) {\n            int len = f(i, 1<<i, words) + words[i].size();\n            if (len < minlen) {\n                minlen = len;\n                minword = i;\n            }\n        }\n\n        string res;\n        res.append(words[minword]);\n\n        int prev = -1, mask = (1<<minword);\n\n        for (int i = 1; i < n; i++) {\n            prev = minword;\n            // find the next word\n            minword = choice[minword][mask];\n            // update the mask to indicate that this word has been used now.\n            mask = mask | (1<<minword);\n\n            int commonPrefix = sufPref[prev][minword];\n\n            res.append(words[minword], commonPrefix, words[minword].size() - commonPrefix);\n        }\n        \n        return res;\n    }\n};\n```
['C++']