In order to successfully solve this task, it was necessary to notice the following: if we construct a prefix tree for a set of words, it is surely optimal to begin constructing the prefix tree so that all letters in common to all words are used as the initial chain of that subtree. For example, if we have words aaab, baab and cab, it is optimal to use letters abc to create a common prefix of all words, and after that, we are left with words aa, ab, c. Now that we don't have any more letters that are in all three words, we need to keep constructing the tree somehow.

Since we know that the remaining suffixes of the three words will not be in the same subtree, because they don't have any letters in common, we select two subsets of words for which we say that from now on are being built in different subtrees. In our case, it is optimal to select (aa, ab) as one subset, and (c) as the other. The subset division is performed in ~2^n~ ways, if there are ~n~ words in the set. Each word can be either in one or the other set in which we divide the words into.

It is also necessary to notice that, even though two words are in the same set, it doesn't mean that they will continue being built in the same subtree for at least one step, but it might be the case that they become divided immediately, recursively.

This kind of thinking leads us to solve the task using dynamic programming, where a state is described with the set of words (a bitmask), and we have ~2^n~ such states. This dynamic programming approach will calculate the size of the smallest tree constructed from these words.

Since we traverse through all subsets of the state in each state, the total complexity is ~\mathcal O(3^n)~.