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?