Complete search (DFS) with simple prunning
Straightforward DFS with the following simple prunning strategy: for every string s we pre-calculate the length of the longest possible overlap between s and an
Straightforward DFS with the following simple prunning strategy: for every string `s` we pre-calculate the length of the longest possible overlap between `s` and any other strings. Then for every possible subset `A\'`of A, we could use the sum of the precalculated lengths as an upperbound to the total overlaps that can be obtained by combining all the strings in `A\'`. Using this upperbound, we could give up early on many branches. \n```\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& A) {\n        g.assign(A.size(), vector<int>(A.size(), 0));\n        max_points.assign(A.size(), 0);\n        \n        for (int i = 0; i < A.size(); ++i) {\n            for (int j = 0; j < A.size(); ++j) {\n                if (i == j) {\n                    continue;\n                }\n                int max_len = min(A[i].size(), A[j].size());\n                for (int t = 1; t <= max_len; ++t) {\n                    if (std::equal(A[i].begin()+A[i].size()-t, A[i].end(), A[j].begin())) {\n                        g[i][j] = t;\n                    }\n                }\n                max_points[i] = max(max_points[i], g[i][j]);\n                max_points[j] = max(max_points[j], g[i][j]);\n            }\n        }\n        \n        for (int i = 0; i < A.size(); ++i) {\n            unused.insert(i);\n        }\n        for (int u = 0; u < A.size(); ++u) {\n            unused.erase(u);\n            path.push_back(u);\n            dfs();\n            path.pop_back();\n            unused.insert(u);\n        }\n        string res = A[max_path[0]];\n        for (int i = 1; i < max_path.size(); ++i) {\n            res += A[max_path[i]].substr(g[max_path[i-1]][max_path[i]]); \n        }\n        return res;\n    } \nprivate:\n    void dfs() {\n        if (unused.size() == 0) {\n            if (sum >= max_sum) {\n                max_sum = sum;\n                max_path = path;\n            }\n            return;\n        }\n        \n        std::vector<int> un;\n        int mp = 0;\n        for (auto u : unused) {\n            un.push_back(u);\n            mp += max_points[u];\n        }\n        if (mp + sum < max_sum) {\n            return; // cut\n        }\n        \n        int prev = path.back();\n        for (auto u: un) {\n            unused.erase(u);\n            path.push_back(u);\n            sum += g[prev][u];\n            dfs();\n            sum -= g[prev][u];\n            path.pop_back();\n            unused.insert(u);\n        }\n    }\n    \nprivate:\n    vector<vector<int>> g;\n    \n    vector<int> max_points;\n    unordered_set<int> unused;\n    int sum = 0;\n    vector<int> path;\n    vector<int> max_path;\n    int  max_sum = 0;\n};\n```
[]