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?