# Return the subset with smallest cardinality of an array whose elements sum to at least a given value

Suppose we are given an array $$A[1\ldots n]$$ and a value $$C$$.

Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $$A[1\ldots n]$$ whose elements sum to at least $$C$$?

• What do you mean by “smallest”? Oct 13 '19 at 9:31
• the subset with the least elements Oct 13 '19 at 9:46
• I mean, the subset with smallest cardinality Oct 13 '19 at 9:54
• Have you tried the greedy approach? Oct 13 '19 at 9:57
• I'm not really sure what the greed approach is Oct 13 '19 at 9:58

## 1 Answer

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