How to find a subset of numbers such that its average is close to the average of the full set? I have a set of n numbers whose average (arithmetic mean) is x. I have to choose a subset of k numbers from n such that its average is closest to x. Please note that k is the upper bound. If the average can be represented with less than k numbers, then that set is chosen.

For example:
set = {1, 2, 3, 4, 5, 6} (n = 6) (average = 3.5)
If k = 1 then the subset can be either {3} or {4}
If k = 2 then the subset is {3, 4}
If k = 3 then the subset is still {3, 4}  

I have to write an algorithm for the same. If this problem is not solvable in polynomial time, what would be a good approach to solve it? Any heuristic approach?
I am not sure if you are allowed to use a solver for this, but this problem can be easily formulated as a Mixed Integer Nonlinear Programming (MINLP) problem.



This can be solved with open source solvers like Couenne or Bonmin. Actually this model can be linearized so it can even be solved with linear Mixed Integer Programming (MIP) solvers.