← All solutions

This problem can be solved by brute force with some pruning. Essentially, we just try to perform the Huffman tree creation backwards: we start with the entire tree defined by the input, for which we know that the frequency is 100 and then try all 50 possible ways of distributing this frequency into its two subtrees (i.e., (1, 99), (2, 98), and so on, up to (50, 50)). We then do the same things for these subtrees, and so on, until all the frequency has been distributed all the way down to the leaves of the tree.

There are two ways to prune this which will make the solution very fast.

The first observation is that, when choosing how to distribute (or split, as I will henceforth call it) the frequencies among the two subtrees of a tree, both of the two “subfrequencies” must be smaller (or equal) than the minimum frequency of any previous split. For instance, if the frequencies of the subtrees of the root were chosen as (40, 60), the right subtree could not have (10, 50) as the frequencies of its subtrees. So in this example, there would only be 11 possible ways to split the 60-tree, rather than 30.

The second observation is that, because of the first observation, we should always split the currently active subtree with the largest frequency. In other words, we do not have to try different orders of splitting the subtrees, there will always be a uniquely determined subtree to do the next split on.