# Find the sum of the first K subsets of integer array

We have given a multiset of $N$ integer, both positive or negative. Consider all $2^N$ subsets, sorted by their sum (the empty subset has sum 0). We want an algorithm that outputs only the first $K$ sums.

The problem is that $N$ can be very big number (up to 100000), so we cannot generate all subsets. How to optimize the search so we wont generate more than $K$ subsets.

$K$ in the problem will also be up to 100000.

I was thinking to get the smallest possible subset and then try to make it bigger and bigger, but I couldn't come to something that will work in all cases.

Say the multiset is $S=M\cup P$ where $M$ is the set of negative numbers and $P$ is the set of non-negative numbers. Define $S^+=(-M)\cup P$ where $-M$ means the set of opposite numbers of elements of $M$. For a subset $T=(-M_T)\cup P_T$ of $S^+$ where $M_T\subseteq M$ and $P_T\subseteq P$, define $f(T)=(M\backslash M_T)\cup P_T$, which is a subset of $S$. Now easy to see $f$ is a bijection, and the sum of $f(T)$ is the sum of $T$ plus a constant (the sum of $M$). So we only need solve the problem on $S^+$, and transform the result, say $T_1,T_2,\ldots, T_K$ to $f(T_1),f(T_2),\ldots, f(T_K)$. That is to say, we only need to solve the problem where all elements are non-negative.

This is solved in this post. For completeness of this answer, I quote it here.

(Going to assume nonempty subsets for simplicity. Handling the empty subset is a line or two.)

Given a nonempty subset of indices S, define the children of S to be S \ {max(S)} U {max(S) + 1} and S U {max(S) + 1}. Starting with {1}, the child relation forms a tree that includes every nonempty subset of positive integers.

{1}
|  \
{2} {1,2}______
|  \     \     \
{3} {2,3} {1,3} {1,2,3}


Keyed by the sum of corresponding array elements, this tree is a min-heap. If you compute the keys carefully (by adding and subtracting rather than summing from scratch) and implement the min-heap deletion lazily, then you get an O(k log k)-time algorithm.