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.
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).