As many has posted here, the answer is simply to sum up the 2nd, 4th, 6th, ...largest values from `nums[]`

. But why?

The problem ca be reduced to prove the following statement:

Let

`P`

be an arbitrary n-pair partition for`nums[]`

,`sum(P)`

be such sum of partition`P`

,`max1`

,`max2`

be the max and 2nd max values in`nums[]`

.

Prove if `max1`

is not paired with `max2`

in `P`

, and we swap `max2`

with the value paired with `max1`

to get partition `P'`

, we must have

`sum(P') >= sum(P).`

**Proof:** Without losing generality, let pairs `(max1, v1)`

and `(max2, v2)`

in partition `P`

and `v1 < max2`

, then `P'`

has the same pairs as `P`

except `(max1, max2)`

and `(v1, v2)`

. We will only need to prove that

`min(max1, max2) + min(v1, v2) >= min(max1, v1) + min(max2, v2)`

.

Note that `min(x, y) = (x+y-|x-y|)/2`

for any number `x, y`

, so we can simplify the inequality above as

`max2 - v1 >= min(max2, v2) - min(v1, v2) = (max2+v2-|max2-v2|-(v1+v2-|v1-v2|))/2`

`= (max2-v1 + |v1-v2| - |max2-v2|)/2`

.

By triangle inequality, actually, the right hand side

`(max2-v1 + |v1-v2| - |max2-v2|)/2 <= (max2-v1 + |max2-v1|)/2 = max2 - v1`

.

And the proof is complete.

Python:

```
def arrayPairSum(self, nums):
return sum(sorted(nums)[::2])
```

C++:

```
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int sum = 0, i = 1;
for (int x : nums) sum += x*(i++%2);
return sum;
}
```