Smallest subset of array whose sum is no less than key

Question

Given an array (lets assume of non negative integers) we are required to find the smallest length subset such that sum of elements is no less than K. K is another integer provided as input.

Is it possible to have a solution with time complexity O(n) [big oh of n]?

my current thinking is along the following lines: we could sort the array in O(n * log n) and then iterate over the sorted array starting from the largest number and maintaining the running sum until the running sum becomes >= K.

However, this would have worst case running time of O(n * (log n + 1)).

So if anyone could share ideas of doing this in O(n) time, I would really appreciate..

Note: The elements of subarray dont have to be a contiguous sequence of the original array in this context

Answer 1

There is a linear time algorithm for finding the K largest numbers - http://en.wikipedia.org/wiki/Selection_algorithm. Of course what you want is just enough largest numbers to sum up to at least K.

In the standard selection algorithm, you take a random pivot and then look to see how many numbers fall on each side of it. You then either accept or reject one half, and keep working on the other half. You have just looked at each number in each half, in turn - the cost of each pivot stage is linear, but the amount of data considered at each stage reduces fast enough that the total cost is still only linear.

The cost of a pivot stage will still be only linear if you take the sum of all the numbers above the pivot. Using this, you can work out if accepting all these numbers, together with any numbers previously selected, would give you a collection of numbers that add up to at least K. If it does, you can ditch the other numbers and use the numbers above the pivot for the next pass. If it does not, you can accept all the numbers above the pivot, and use the numbers below the pivot for the next pass. As with the selection algorithm, the pivot itself and any ties give you a few special cases and the possibility of finding an exact answer early.

(So I think you can do this in (randomized) linear time using a modified version of the selection algorithm in which you look at the sum of the numbers above the pivot, instead of how many numbers are above the pivot.