You can use meet-in-the-middle to reduce the running time to $O(n^{\lceil k/2 \rceil})$.
For simplicity, let me assume that $k$ is even.
The idea is as follows:
* Partition $A$ into two parts.
* For each part, compute a sorted list of sums of $k/2$ elements from the part.
* For each $k/2$-sum in the first part, use binary search to find the best $k/2$-sum in the second part which conforms to the constraints.
As stated, there are several problems with the idea:
1. It assumes that the optimal solution contains exactly $k/2$ summands out of each part.
2. It runs in time $O(n^{k/2} \log n)$.
3. It uses $O(n^{k/2})$ memory.
To handle the first difficulty, there are several options. We could just repeat the entire algorithm $\sqrt{k}$ times. Alternatively, there might be deterministic ways to achieve the same goal. 743
Here is a hybrid solution:
* Randomly partition $A$ into $k^3$ parts $P_1,\ldots,P_{k^3}$ (anything substantially larger than $k^2$ would work). With high probability, each element of the optimal solution is in its own part.
* Consider all possible partitions of $A$ into two parts of the form $P_1,\ldots,P_i$ and $P_{i+1},\ldots,P_{k^3}$. One of these will contain exactly $k/2$ elements of the optimal solution.
To handle the second difficulty, we need to be slightly more careful in implementation. Using merging (the familiar subroutine from mergesort), it should be possible to compute the $k/2$-sums of each part in $O(n^{k/2})$. The final step can be implemented in $O(n^{k/2})$ using a classic two-pointer technique (the first pointer goes up on the first half, the second one goes down on the second half).
There are tricks to reduce the memory required from $O(n^{k/2})$ to $O(n^{k/4})$: further divide each part into two sub-parts. You can easily go over all $k/2$-sums in the first part by considering all pairs of $k/4$-sums in its subparts. Binary search on the second part can then be implemented using the two-pointer technique. 743