# Determine if an array is divisible in pairs of equal sum

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?

• Well it wouldn't necessarily give an equal sum every time. This can easily be seen by replacing, the 8 with 10. The reason your example seems symmetric is because you are adding 1 to every element on your LHS and subtracting 1 from every element on your RHS. May 19, 2018 at 13:12

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.