Return the subset with smallest cardinality of an array whose elements sum to at least a given value
First, we randomly select an element that is not the smallest one as a pivot, and partition the elements into two subsets: the ones less than the pivot ($P$) and the ones no less than the pivot ($Q$). Let $S$ be the sum of elements in $Q$. 


If $S=C$, then $Q$ is exactly the optimal subset we want. 
If $S&lt;C$, then the optimal subset is the union of $Q$ and the subset with smallest cardinality of $P$ whose elements sum to at least $C-S$, which can be found by recursively applying this algorithm on $P$.
If $S&gt;C$, then the optimal subset is the subset with smallest cardinality of $Q$ whose elements sum to at least $C$, which can be found by recursively applying this algorithm on $Q$.


Let $T(n)$ denote the expected running time of this algorithm on an input of $n$ elements, we have
$$T(n)\le \frac{1}{n-1}\sum_{i=1}^{n-1} T(\max\{i,n-i\})+cn,$$
where $c$ is a constant. By mathematical induction we can conclude that $T(n)\le 4cn$, thus the algorithm runs in expected linear time.



You can also use the idea of median-of-medians to get a worst-case linear time algorithm by selecting the pivot as the apporximate median produced by the median-of-medians algorithm.