I have first sorted the array of subsets in decreasing order.

then the first element of this array s[0] will contain sum of all elements that would be present in the original array.

the s[1] will contain sum of (n-1)largest numbers of the original array

thus s[0]-s[1] will result in smallest element of the original array.

now s[2] will contain sum of (n-2)largest elements & 1 smallest element of original array.

thus s[0]-s[2] will be the second smallest element of the original array.

similarly other elements of the array can be found.

but I am getting wrong answer for this approach.

please correct it, if any errors are there.

m solution link is http://www.codechef.com/viewsolution/5189854

this is in general wrong for instance letâ€™s take small value of n=3 s.t. a=1,b=2,c=5 then according to you s[0]=a+b+c which is true and the approach will continue to be true till s[2] as s[2]=a+c but this approach fails in this case when you reach s[3] acc. to you s[3]=a+b but actually s[3]=c so s[0] -s[3]=a+b and not equal to c.

2 Likes