leet_891

README

题解

这实际是一道数学题，首先可以把A数组排序。对于排序后的A[i]，如果它的值被计算，要么它是某个子集的最大值，要么是某个子集的最小值。A[i]如果是集合的最大值，这种集合有多少个呢？很显然，可以从A[0..i-1]这i个元素中任选一些：

• 当从A[0..i-1]中选一个和A[i]组成2个元素的集合，一共有C(i,1)种
• 当选两个元素和A[i]一起组成3元素集合时，一共有C(i,2)种
• ...
• 当把A[0..i-1]全部选上，可以和A[i]组成一个有i+1个元素的集合，有C(i,i)=1种

因此，A[i]作为最大值的集合有∑ C(i,k) (k属于[1,i])种，根据二项式定理，它的值其实就是(2^i)-1。

同理，如果A[i]作为集合的最小值，一共有2^(N-i)-1个这样的集合。

由于题目是求所有集合(最大值-最小值)的和，相当于所有集合的最大值的和 - 所有集合的最小值的和。

所以对于A[i]来说，它个最大值的和贡献了A[i](2^i -1)，它给最小值的和贡献了A[i](2^(N-i) -1)，枚举所有A[i]即可。