一个集合子集的个数怎么计算（5分钟练脑算法题）

【题目】

给一个集合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 ){ ....... } } } }

如果有觉得有意思，欢迎转发收藏~~

,