Find the sum of the first K subsets of integer array
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.