集合求和

题意

给定一个集合，求所有子集中所有元素的和。

思路

设集合有 n 个元素。对任意一个元素来说，其他 n-1 个元素都可以选或不选，因此包含它的子集有：

text

12^(n-1)

所以每个元素都会被加 2^(n-1) 次，答案就是：

text

1sum(numbers) * 2^(n-1)

这题关键是数学计数，不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：输入没有给数量时，可以直接 input().split() 读取整行元素。
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：Python 整数不会溢出，能直接处理本题答案范围。
sum(numbers) 求列表总和。
2 ** k 表示 $2^k$ 。

代码

python

1
2
3numbers = list(map(int, input().split()))
answer = sum(numbers) * (2 ** (len(numbers) - 1))
print(answer)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

int a[35]; // 集合元素
int n;     // 元素个数

int main() {
    int x;
    while (cin >> x) a[++n] = x;
    // 每个元素在 2^(n-1) 个子集中出现
    long long sum = 0;
    for (int i = 1; i <= n; i++) sum += a[i];
    long long ans = sum * (1LL << (n - 1)); // 等价于 sum * 2^(n-1)
    cout << ans;
    return 0;
}

Pythonic 写法

子集和位运算：

python

1
2nums = list(map(int, input().split()))
print(sum(nums) << (len(nums) - 1))

复杂度

设元素个数为 n，时间复杂度是 $O(n)$ ，空间复杂度是 $O(n)$ 。

总结

不要枚举所有子集。换个角度统计每个元素贡献次数，就能把指数问题变成一次求和。

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结