Given a list of $n$ real numbers: $R=(r_1,r_2,\ldots,r_n)$ with $r_i < r_{i+1}$, and a target real number $t$, How can we find the subset of $R$ of size $k$ with a sum that best approximates $t$? I have no idea how to do this well for $k>2$ but I think that there should be an $n \log n$ algorithm.
This is what I know so far.
Case: $k=1$
Since the list is sorted you can find the $r_i$ that is closest to $t$ in $\mathcal{O}(\log n)$ time via binary search.
Case: $k = 2$
Start with $i = 1$ and $j = n$. While $i \le j$: if $(r_i+r_j) >t$ decrement $j$; else if $(r_i+r_j) < t$ increment $i$. Keep track of the best approximation as you go along. This is $\mathcal{O}(n)$
Case: $k=3$
Can we do better than $\mathcal{O}(n^2)$??
Case: $k>3$
??
Apparently for general problems at $k=3$ the answer is: "No, we cannot do better than $\mathcal{O}(n^2)$." However for some structured problems you can do much better. I guess it really depends on the problem and is a topic of ongoing research.
For $k>3$ the only known result is that you can do $\Omega(n^{\textrm{ceiling}(k/2)})$