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)

but i did not really understand how its working .

can some give a detail explanation?