# 集合求和 ## 题目描述 给定一个集合 $s$（集合元素数量 $\le 30$），求出此集合所有子集元素之和。 ## 输入格式 集合中的元素（元素 $\le 1000$） ## 输出格式 $s$ 所有子集元素之和。 ## 样例 #1 ### 样例输入 #1 ``` 2 3 ``` ### 样例输出 #1 ``` 10 ``` ## 提示 **【样例解释】** 子集为：$\varnothing, \{ 2 \}, \{ 3 \}, \{ 2, 3 \}$，和为 $2 + 3 + 2 + 3 = 10$。 ---- **【数据范围】** 对于 $100 \%$ 的数据，$1 \le \lvert s \rvert \le 30$，$1 \le s_i \le 1000$，$s$ 所有子集元素之和 $\le {10}^{18}$。

以下是C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

long long sum = 0;
vector<int> nums;

void dfs(int index, long long path_sum) {
    if (index == nums.size()) {
        sum += path_sum;
        return;
    }
    dfs(index + 1, path_sum + nums[index]);  // 加上当前元素
    dfs(index + 1, path_sum);  // 不加当前元素
}

int main() {
    int n;
    cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    dfs(0, 0);
    cout << sum << endl;
    return 0;
}

思路解析：

使用深度优先搜索（DFS）算法，遍历集合 $s$ 的所有子集，累加子集中所有元素之和，即可得到答案。

DFS 算法的实现：

- 对于集合 $s$ 中的每个元素，有两种选择：将其加入子集，或不加入子集。
- 对于每个子集，都累加其中所有元素的和，得到当前子集的元素之和。
- 遍历完所有子集后，将所有子集的元素之和累加起来，得到最终答案。

时间复杂度：$O(2^n)$，其中 $n$ 为集合 $s$ 的元素个数。

空间复杂度：$O(n)$，其中 $n$ 为集合 $s$ 的元素个数，主要消耗的空间为递归栈空间。