Algorithm to find the optimal setup Suppose I have $2n$ numbers, from which I will compute $n$ sums of two-number pairs. For example, I have $6$ numbers $(1, 2, 3, 4, 5, 6)$ and I can generate three sums of $1+3=4$, $2+6=8$, and $4+5=9$. Each number has to be used once and only once. There are totally $\frac{(2n)!}{2^n n!}$ possible lists of outcomes. Note that these $2n$ numbers can be any values, not necessarily integers. This is just a simple example for illustration.
My goal is to make these sums as close to my target value as possible on average. Suppose my target value is $7$. If the pairs are $(1, 3), (2, 6), (4, 5)$, their sums are $4, 8, 9$. The difference to my target $7$ is defined as $|4-7|+|8-7|+|9-7|=6$. However, if a different pair lists $(1, 6), (2, 5), (3, 4)$ is used, the difference to the target would be $|7-7|+|7-7|+|7-7|=0$. So the latter setup is closer to the target on average. This is actually the optimal choice in all possible outcomes.
My question is if there is a good computing algorithm to find the optimal choice of pairs, instead of computing all $\frac{(2n)!}{2^n n!}$ possibilities.
BTW: what if the difference on average is defined by sum of squares $(4-7)^2+(8-7)^2+(9-7)^2$?
 A: It seems to me that if the integers are ordered from $1$ to $2n$, the optimal solution will always be summing the $i^{th}$ integer with integer $2n - i + 1$, basically meaning summing the largest with the smallest and performing this recursively. This is exactly how it turned out in your example. 
This makes sense intuitively, because if the target is large, summing two larger numbers together will come closer to the solution but will make the smaller numbers required to be summed together differ from the solution by at least the same amount as gained if not more. The same holds if the target is small, and is analogous if the target is mid-ranged. 
A: Here are my thoughts that are way better than searching exhaustively.
First take your set and shift each, $$(1,2,3,4,5,6) \rightarrow (1-\frac{7}{2}, 2-\frac{7}{2}, \ldots \text{etc})$$
This gives the target value of zero.
Now when your set of numbers is shifted in this way, the numbers are easily compared. The largest negative needs be combined with the largest positive, that is the only way to obtain the least error for that large number. This method would easily find the best for your small example. I am not sure, but this maybe is the best way, at least for pairing (if you wanted $3$ and only $3$ instead of $2$ for each sum, I believe that very much complicates things raising the difficulty.)
There is also a matching algorithm (I will let you know if I can remember the name) that I read that works by comparing possible discrete (single) changes, keeping the improvements. Let me attempt a description that may lack good terminology or symbols (sorry).
Basically in your example you start with $(1,3) \quad (2,6) \quad (4,5)$ and look at the $(1,3)$ as it has the most error. Then find if any improvement may be had with re-ordering:
\begin{align}
  (1,3)\Delta 3 & (2,6)\Delta 1 & \Delta_{\text{total}} = 4\\
  (1,6)\Delta 0 & (2,3)\Delta 2 & \Delta_{\text{total}} = 2 &\text{improvement- keep}
\end{align}
At this point your set is now $$(1,6) \quad (2,3) \quad (4,5)$$
And the total error that was $6$ is reduced to $4$. From here you hopefully can see that the next comparison reaches the ideal. I am not sure if this type of algorithm is needed for your example, as I believe that matching the least number with the largest number, then repeating as I described in the first paragraph, would be all that is needed.
