# List the smallest $k$ subset sums

Given a set of positive reals ${x_{1},…,x_{n}}$ where $x_{1}<x_{2}<…<x_{n}$, find the smallest $k$ subset sums.

We can assume $n≤k$, because we do not have to read $x_{j}$ if $j>k$.

Torsten Gross and Nils Blüthgen posted a $O(k_{2})$ time solution on arXiv.

We show a $O(kgk)$ 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 $I⊂[n]$ (that is, $∑_{i∈I}x_{i}$) into the output, let $j=1+maxI$. Now we can consider two possibilities by extending the current solution: the sum induced by $I∪{j}$ or the sum induced by $I∪{k}$ where $k>j$. 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.

```
def first_k_subset_sums(x,k):
= len(x)
n = []
h = [0] # need to account for the empty set
output 0],0))
heapq.heappush(h,(x[while h and len(output)<k:
= heapq.heappop(h)
(u,b)
output.append(u)if b+1<n:
+x[b+1],b+1))
heapq.heappush(h,(u-x[b])+x[b+1],b+1))
heapq.heappush(h,((ureturn output
```

If we want to output the sets themselves, not just the values, does the running time change? If a set $I$ is in the output, then all subsets of $I$ must also be in the output. Hence the largest set we can ever output has size $O(gk)$. Therefore the total output length is at most $O(kgk)$.

This is also a lower bound. Consider when $x_{i}=2_{i}$, then we will output all subsets of ${x_{1},…,x_{logk}}$, and we know that $∑_{i=1}i(ilogk )=Ω(gk)$.

If we don’t have to list the smallest $k$ subset sum values in order, then $O(k)$ is possible, see this mathoverflow answer by David Eppstein.

If we are interested in the smallest $k$ *distinct* subset sum. I don’t know
of any algorithm that performs better than $O(nk)$, even if we know that $n=Ω(k)$.

# Acknowledgements

I would like to thank Tana Wattanawaroon for helpful discussions and taking an interest in this problem.