title: How to generate k largest subset sums for a given array (contains positive and negative numbers)
body: <p>So the question is pretty straight forward, given an array of size N( N&lt;=10^5) , we want to generate k greatest subset sums where k is in worst case MIN of (2000 and 2^N).</p>
  <p>We have to output in the decreasing order.</p>
  <p>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,</p>
  <p>Asked in amazon OA(question is called find k maximum priority)</p>