How to generate k largest subset sums for a given array (contains positive and negative numbers)-CodePudding

So the question is pretty straight forward, given an array of size N( N<=10^5) , we want to generate k greatest subset sums where k is in worst case MIN of (2000 and 2^N).

We have to output in the decreasing order.

Is there any way to do this in less than exponential complexity. My thinking is that If we have to generate 2^N items , how can the complexity be less than 2^N,

Asked in amazon OA(question is called find k maximum priority)

CodePudding user response：

I'll just outline it. It is up to you to implement it and show that it works.

First, in a single pass, we find the sum of the positive numbers. This is the maximum sum. We initialize our answer array with [maximum_sum].

Next, we create an array av of the absolute values, sorted from smallest to largest.

Next, we create a priority queue upcoming. It will start with one pair in it. That pair will be (maximum_sum - av[0], 0). The pairs are compared lexicographically with largest sum first.

Until we have enough elements in answer we will:

get (next_sum, i) from upcoming
add next_sum to answer
if i < N:
    add (next_sum   av[i] - av[i 1], i 1) to upcoming
    add (next_sum - av[i 1], i 1) to upcoming

This algorithm will take O(N k) memory and O(N log(N) k log(k)) work to generate the top k answers. It depends on both N and k but is exponential in neither.