List the smallest subset sums
Given a set of positive reals where , find the smallest subset sums.
We can assume , because we do not have to read if .
Torsten Gross and Nils Blüthgen posted a time solution on arXiv.
We show a time algorithm, which is optimal if we want to output the numbers in order.
We list the sums one by one by maintaining a priority queue of sums. We start with the empty set. Assume that we added the sum induced by (that is, ) into the output, let . Now we can consider two possibilities by extending the current solution: the sum induced by or the sum induced by where . We will add both possibilities to the queue so that one can inspect them later. We can avoid storing the sets, only the values are required.
Here is a python implementation.
If we want to output the sets themselves, not just the values, does the running time change? If a set is in the output, then all subsets of must also be in the output. Hence the largest set we can ever output has size . Therefore the total output length is at most .
This is also a lower bound. Consider when , then we will output all subsets of , and we know that .
If we are interested in the smallest distinct subset sum. I don’t know of any algorithm that performs better than , even if we know that .
I would like to thank Tana Wattanawaroon for helpful discussions and taking an interest in this problem.