java - How to find Sum of differences of maximum and minimum of all possible subset of an array

Question

how to Find sum of maximum- minimum of all possible subset of given array

for example

given array is 1 all posible subsets are [[], [1]] 1-1=0

given array is 1 2 all posible subsets are [[], [1], [2], [1, 2]] 1-1+2-2+2-1=1

given array is 1 2 3 all posible subsets are [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 1-1+2-2+2-1+3-3+3-1+3-2+3-1=6

given array is 1 2 3 4 all posible subsets are [[], [1], [2], [1, 2], [3], [1, 3], [4], [2, 3], [1, 4], [1, 2, 3], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]] ans=23

given array is 2 3 4 5 all posible subsets are [[], [1], [2], [1, 2], [3], [1, 3], [4], [2, 3], [1, 4], [5], [1, 2, 3], [2, 4], [1, 5], [1, 2, 4], [3, 4], [2, 5], [1, 3, 4], [1, 2, 5], [3, 5], [2, 3, 4], [1, 3, 5], [4, 5], [1, 2, 3, 4], [2, 3, 5], [1, 4, 5], [1, 2, 3, 5], [2, 4, 5], [1, 2, 4, 5], [3, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5], [1, 2, 3, 4, 5]] ans= 72

Answer 1

First of all, sort the array then the i'th element will be minimum in all subsets that do not include the i-1 first elements, and include this element. There will be 2^(n-i) of those. In the same way, i will be the highest element in each subset that does not include any number after i, and include i, and there are 2^(i-1) such subsets.now iterate and for each i add:

sum = sum + array[i] * (2^(i) - 2^(n-i-1))
//if array starts with index array[0]

Consider your example: [1,2,3]

sorted=1,2,3
1* (2^0 - 2^2) + 2*(2^1 - 2^1) + 3*(2^2 - 2^0) =
1*(-3) + 2*0 + 3*(3) = -3 + 0 + 9 = 6