BackTracking+DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\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\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```csharp []\npublic class Solution {\n   \n    private int CommonChars(string a, string b)\n    {\n        int len = a.Length;\n        if(len == 0 || b.Length == 0)\n            return 0;\n\n        int minLen = Math.Min(len, b.Length);\n        while(minLen > 0)\n        {\n            string p1 = a.Substring(len-minLen), p2 = b.Substring(0, minLen);\n            if(p1 == p2)\n                break;\n\n            minLen--;\n        }\n\n        return minLen;\n    }\n    private string[,] remains;\n    private string BackTracking2(string[] words, int start, int mask, int len, string[,] dp)\n    {\n        if (dp[start, mask] != "")\n            return dp[start, mask];\n\n        int minLen = int.MaxValue;\n        string res = "";\n        for (int i = 0; i < len; i++)\n        {\n            if ((mask & (1 << i)) == 0)\n            {\n                string temp = remains[start, i] + BackTracking2(words, i, mask | (1<<i), len, dp);\n                if (temp.Length <minLen)\n                { \n                    minLen = temp.Length;\n                    res = temp;\n                }\n            }\n        }\n\n        dp[start, mask] = res;\n        return res;\n    }\n\n\n    public string ShortestSuperstring(string[] words) {\n        int len = words.Length, minLen = int.MaxValue;\n        if (len == 0)\n            return "";\n        if (len == 1)\n            return words[0];\n        string[,] dp = new string[len, (1<< (len+1))];\n\n        remains = new string[len, len];\n        for (int i = 0; i < len; i++)\n        {\n            for (int j = 0; j < len; j++)\n            {\n                remains[i, j] = "";\n            }\n\n            for (int k = 0; k < dp.GetLength(1); k++)\n            {\n                dp[i, k] = "";\n            }\n        }\n\n\n        for (int i = 0; i < len - 1; i++)\n        {\n            for (int j = i + 1; j < len; j++)\n            {\n                int p1 = CommonChars(words[i], words[j]);\n                int p2 = CommonChars(words[j], words[i]);\n                remains[i, j] = words[j].Substring(p1);\n                remains[j,i] = words[i].Substring(p2);\n            }\n        }\n        int mask = 0;\n\n        string res = "";\n\n        for (int i = 0; i < len; i++)\n        {\n            string tmpStr = words[i] + BackTracking2(words, i, mask |(1<<i), len, dp);\n            if (tmpStr.Length < minLen)\n            {\n                res = tmpStr;\n                minLen = tmpStr.Length;\n            }\n        }\n\n        return res;\n\n    }\n}\n```
['C#']