Determine if an array is divisible in pairs of equal sum

Question

I'm currently studying the time complexity of the solution provided by my teacher to this problem, and I can't understand the logic:

Let A be an unordered array of positive natural numbers. Write an algorithm that checks if it's possible to divide A into pairs (subsets of two elements) of equal sum.

Example [1 7 4 2 4 0 8 6] is composed of 1+7, 4+4, 2+6 etc all of which give 8.

Now, the solution works like this: it sorts the array, and then checks if the sum of $A[i]$ and $A[length-i]$ (indexes start at 1) always give the same value.

Example: [0 1 2 4 4 6 7 8] is the above array after reordering. Checks 0+8=8, then 1+7=8, then 2+6=8 etc.

So the algorithm returns True, since every $(n,n-i)$ pair in the array always gives the same sum.

My problem with this is that I can't understand why positioning the elements with this symmetry would give an equal sum everytime.

Why taking the $i$ and $n-i$ elements would give the same sum?

Answer 1

For simplicity, let's pretend there are no duplicates in your array. The answer generalizes easily to arrays containing duplicates.

If the array can be divided into pairs of equal sum, then the lowest number (on place $0$ in the sorted array) and the highest number (on place $n$ in the sorted array) has to be a pair. We can do a proof be contradiction by assuming that the lowest number ($x_0$) and the highest number ($x_n$) is not a pair. As all numbers in the array needs to be in a pair, this implies that $x_0$ is in a pair with an other number $x_j$ and likewise that $x_n$ is in a pair with $x_k$. As $x_n$ is the highest number, it must be that $x_j \lt x_n$ and therefore, in order for $x_o + x_j$ to be equal to $x_k + x_n$ it must be that $x_k \lt x_0$ but this goes against our assumption that $x_0$ is the lowest number.

Having proved that $x_0$ and $x_n$ is a pair, the same proof now goes for $x_1$ and $x_{n-1}$ and recursively for the whole array.

Answer 2

You sort the array in increasing order.

If you pair an element equal to the largest element with any element that is larger than the smallest element, then pairing the smallest element with any other element will give a smaller sum, and therefore a different sum.

Therefore, to find pairs that all have the same sum, you must pair an element equal to the largest with an element equal to the smallest, and then repeat for the remaining elements. This will give you pairs with equal sums if it is possible. If not possible, then of course you won't get equal sums.