730. 所有子集的和递归
730. 所有子集的和递归
和蔼的zhxing
发布于 2018-09-04 11:34:05
发布于 2018-09-04 11:34:05
给一整数 n, 我们需要求前n个自然数形成的集合的所有可能子集中所有元素的和 样例
给出 n = 2, 返回 6
可能的子集为 {{1}, {2}, {1, 2}}.
子集的元素和为 1 + 2 + 1 + 2 = 6
给出 n = 3, 返回 24
可能的子集为 {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
子集的和为:
1 + 2 + 3 + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24递归
这是个数学题，找到规律就容易做了。 我们从零开始看。
看红色的，是每一个相对于上一个增加的子集，红色的把绿色的去掉就是上一个全部的子集，n的子集应该有一个n-1子集的两倍，还多了什么呢？就是多了很多个n，有多少个呢，就是n-1的子集数，这个值应该是2^n-1。看规律容易看来，另外也是可以推导的： n个自然数取组合数应该是：
这个是高中学的，很简单，二项式定理。 这样分析完之后写程序就简单了：
int subSum(int n) {
long long res=0;
if(n==0)
res=0;
else
res=2*subSum(n-1)+n*pow(2,n-1);
return res;
// write your code here
}递归当然是可以用循环写的：
int subSum(int n) {
long long res=0;
if(n==0)
res=0;
else
for(int i=0;i<=n;i++)
{
res=2*res+i*pow(2,i-1);
}
return res;
// write your code here
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.01.24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录