I am trying to find a divide and conquer algorithm to solve this problem in O(n) but I didn't find anything. given an array A and given value k. find the smallest subset with a sum greater or equal to k. Can someone give me an idea to start solving the problem?
Any help is much appreciated.
Sort the array, then choose elements from largest to smallest until the sum is large enough. The time complexity of this approach will be O(n log n).
When a small subset is expected to be found, a lower average time complexity can be achieved by using the quicksort algorithm and not sorting the lower partition unless and until it turns out to be necessary to do so; when a subset with sufficiently large sum is found in the higher partition, the lower partition can be ignored. If the expected size of the subset is independent of n then the time complexity of this approach should be O(n).
Use quickselect to do this in expected linear time.
Your first quickselect will split the array into two parts, one with larger elements and the other with smaller elements. If the sum of the larger elements is > k, iterate on it. Otherwise, iterate on the other half with a target of k - sum(larger elements).
