算法问题 - 求集合所有子集之和

今天从 iGeekBar 上看到一个有趣的算法题，拿出来和大家分享。

【题目】

给一个集合array，包含n个数。
规定集合的"值"为集合中所有元素的和。
求该集合的所有子集的值的和。

【示例】

数组[1,2]
它的子集有空集[],[1],[2],[1,2]
子集各自的值为0，1，2，3
所以子集值的和为0+1+2+3=6

【解法一】
思路：简单暴力的方法就是穷举数组所有的子集，然后逐个求子集的值，然后相加得到最终的结果。

缺点：时间复杂度高，每个集合的子集个数为2^n个。

实现：
太麻烦了，不实现了。

【解法二】
思路：通过计算每个元素在求和过程中出现的次数，尝试获取一种规律。

[1]==> 0+1=1 // 1出现一次
[1,2]==>0+1+2+(1+2)=6 // 1出现2次，2出现2次
[1,2,3]===>0+1+2+3+(1+2)+(1+3)+(2+3)+(1+2+3)=24 // 1,2,3出现4次

好像有点规律了，每个元素在求和过程中出现的次数是一样的。假设出现的次数是N。

sum = (1+2+3+4+...+n) * N

N的值又和数组的长度有关系，N=2^(n-1)

sum = (1+2+3+4+...+n) * 2^(n-1)

【实现】

var childrenArraySum = function(array){
    var sum = array.reduce(function (a,b) {
        return a+b;
    })
    return sum * Math.pow(2, array.length-1);;
};

childrenArraySum([1,2,3]); // 24

第二种解法的思路很巧妙，把原本很复杂的问题用简单的方式解决了。算法或者说数学对程序员的影响还是很大的。如果在工作中能多思考一下又没有更简单的方法，下面这种写法就不会出现了。

if(a){
  for(var i=0;i<arr1.length;i++){
   if(b){
     for(var j=0;j<arr2.length;j++){
       .......
      }
    }
  }
}

如果有理解不对的地方，欢迎交流指正~~