# 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?

• Your problem should be hard. You can get a good solution by random sampling. – Yuval Filmus Dec 24 '15 at 14:03
• Do you know the target average value in advance or is it unknown ? – StephenG Dec 25 '15 at 15:18
• The target value is not known in advance – user2206344 Dec 28 '15 at 2:37 