2
$\begingroup$

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.

The problem is from past csacademy contest: https://csacademy.com/contest/round-79/task/smallest-subsets/

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.