Commented bitmasking dp solution beats 99.5% runtime and 90% memory
ApproachStandard dp approach where states are a bitset representing which indices are included along with the last index and the value is the length of the shor
# Approach
Standard dp approach where states are a bitset representing which indices are included along with the last index and the value is the length of the shortest possible string matching the state requirements. We then backtrace the dp to find a minimal sequence of strings that produces the optimal result. 

The performance gains come from using 1D arrays to reduce indirection and improve cache locality. We create a lookup table that maps popcount to states so that our dp iterations are efficient. Finally we use some bitmasking tricks to iterate over valid transitions more efficiently (roughly 2x performance increase compared to looping over all combinations and skipping invalid ones) 

getOffset method could be improved using a table based string matching algorithm. This would reduce that portion from $O(n^2w^2)$ to $O(n^2w)$ this would actually make an appreciable difference for $n=12$ but I didn't want to focus on that aspect. 

# Complexity
- Time complexity: $$O(n2^n + n^2w^2)$$ where $n$ is the number of words and $w$ is the maximal word length.
$$O(\sum_{k = 0}^n k(n-k)2^k) \equiv O(n2^n)$$ For the dynamic programming step. $$O(n^2w^2)$$ to compute the transition matrix between words, $$O(n^2 + nw)$$ to backtrace the dp and determine the minimal string.  

- Space complexity: $$O(n2^n + wn)$$
$$O(n2^n)$$ for the states, an additional $$O(2^n)$$ for the state lookup, $$O(n^2)$$ for the offset matrix, and $$O(wn)$$ to construct the minimal string. 

# Code
```cpp []
class Solution {
public:
    string shortestSuperstring(vector<string>& words) {
        size_t sz = words.size();
        size_t mask = (1 << sz) - 1;
        vector<int> offsets(sz * sz, 0);
        for(size_t i = 0; i < sz; i++) {
            for(size_t j = 0; j < sz; j++) {
                offsets[sz * i + j] = getOffset(words[i], words[j]);
            }
        } 
        // distribute states into buckets according to their size 
        vector<vector<size_t>> popcounts(sz + 1);
        for(size_t i = 0; i < (1 << sz); i++) {
            popcounts[__builtin_popcount(i)].push_back(i); 
        }
        // prepare the actual dp: combination of mask and last element
        vector<int> dp(1 << (sz + 4), INT_MAX); 
        // seed initial values 
        for(size_t i = 0; i < sz; i++) {
            dp[(1 << (i + 4)) | i] = words[i].size();
        }
        // perform dp on states
        // we need to consider all possible transitions 
        // j represents the index of a set bit in the state and i is the index of an unset bit in the state

        // we iterate over the number of set bits, propagating forward
        for(size_t n = 1; n < sz; n++) {
            // for each possible bitset 
            for(size_t state: popcounts[n]) {
                // we iterate over the set bits in the complement 
                // equivalent to iterating over the unset bits
                size_t comp_bits = (~state) & mask;
                while(comp_bits > 0) {
                    // bitmasking trick to isolate the least significant set bit 
                    size_t cbit = comp_bits ^ (comp_bits & (comp_bits - 1));  
                    // convert the bit to an index 0b100 -> 2
                    size_t i = std::countr_zero(cbit); 
                    // here we iterate over the set bits
                    size_t state_bits = state;
                    size_t next = state | cbit; 
                    while(state_bits > 0) {
                        // same bitmasking trick as before
                        size_t sbit = state_bits ^ (state_bits & (state_bits - 1));  
                        size_t j = std::countr_zero(sbit);
                        // the transition itself is very simple 
                        // we append string i to a string ending in j, and lengthen it according to the overlap 
                        // we take the minimum over the new value and previous value 
                        dp[(next << 4) | i] = min(dp[(next << 4) | i], dp[(state << 4) | j] + offsets[sz * j + i]);
                        // unset the bit so we can find the next least significant bit
                        state_bits ^= sbit;
                    }
                    // unset the bit so we can find the next least significant bit
                    comp_bits ^= cbit;
                }
            }
        }
        // in the first pass we find the state that has minimal length and contains every word
        size_t backtrack = (1 << sz) - 1;
        // for the first pass we do not have a previous word and we don't know the length
        size_t prev = -1;
        size_t len = 0;
        // the output string to be constructed 
        string output;
        // iterate until we have recovered a minimal sequence (there might be more than one!) 
        while(backtrack > 0) {
            // this will hold the index of the optimal word, working from the end towards the beginning 
            size_t best = 0;
            for(size_t i = 0; i < sz; i++) {
                if(dp[(backtrack << 4) | i] == INT_MAX) {
                    continue;
                }
                if(prev < sz) {
                    // find the first valid transition during all subsequent iterations 
                    if(dp[(backtrack << 4) | i] + offsets[sz * i + prev] == len) {
                        best = i;
                        break;
                    }
                }
                // during the first iteration we find the smallest possible value 
                if(dp[(backtrack << 4) | i] < dp[(backtrack << 4) | best]) {
                    best = i;
                }
            }
            len = dp[(backtrack << 4) | best];
            if(output.size() == 0) {
                output.resize(len);
            }
            copy(words[best].begin(), words[best].end(), output.begin() + len - words[best].size()); 
            // we are now interested states that transition into this state
            // this means that the most recent word index will be unset! 
            backtrack ^= (1 << best); 
            prev = best;
        }
        return output;
    }
    // the rest of the algorithm is sufficiently heavy that I am content writing something suboptimal here
    // this function returns how much the string will grow if string first is followed by string second 
    // we cache these results into a transition matrix 
    int getOffset(const string& first, const string& second) {
        for(int i =0; i < first.size(); i++) {
            // in case the second word is a terminal substring of the first word
            for(int j = 0; j <= second.size(); j++) {
                if(i + j == first.size()) {
                    return second.size() - first.size() + i; 
                }
                if(second[j] != first[i + j]) {
                    break;
                }
            }
        }
        return second.size();
    }
};
```
Questions and feedback are both welcome :)
['Dynamic Programming', 'Bit Manipulation', 'C++']