企业官网建设流程全解析

群里有同学连着抛出两个问题：一个集合的所有子集，把每个子集的元素加起来，再把这些和全部相加，得到多少？另一个问题反过来，把每个子集的元素乘起来，再把这些乘积全部相加，又得到多少？两个问题摆在一起特别有意思——表面上都是"枚举所有子集，做一次运算，最后求和"，但真正动手推下去会发现，它们背后的数学结构完全不同。一个答案是所有元素之和乘以 2 的 n-1 次方，另一个答案却是把每个元素加 1 之后再全部乘起来。我第一次同时接触到这两个问题的时候，差点以为它们是同一个结论的两种写法，直到我把集合 {1,2,3} 的所有子集一个个列出来才算服气。

这篇文章我就把这两个问题从头到尾拆一遍：先从定义说起，再给暴力枚举的代码做基准，然后分别推导两个通项公式，最后用生成函数把它们统一到一个框架里，顺带聊聊实战中会遇到的大数取模、负数、以及几个高频变体。无论你是准备算法面试、打竞赛，还是纯粹想搞懂组合计数里的"贡献法"，这篇都能给你一点可以落地的思路。

1. 先把题目说清楚：这里的"和"和"乘积"分别指什么

这两个问题看起来直白，但描述里藏着几个容易踩的模糊点。第一个问题"求集合的所有子集的之和"，我理解为：对每个子集，先求子集内所有元素的和，再把所有子集的这些"元素和"加总。第二个问题"求集合中所有子集的乘积之和"就是对称的：对每个子集，先求子集内所有元素的乘积，再把所有子集的这些"元素乘积"加总。

为了后面推导不混乱，我用一个固定的例子贯穿全文：集合 S = {1, 2, 3}。它的全部子集一共 2³ = 8 个，逐个列出来看最直观：

这个表里有一个约定需要特别说明：空集的元素和按 0 算，空集的元素乘积按 1 算。0 是加法的单位元，1 是乘法的单位元，这是数学上的自然约定。如果不这样约定，两个问题的公式都会变得不完整，后面讲到乘积之和时我会再解释为什么 1 这个约定如此关键。

另外一个值得提的点是"集合"这个说法。在高中数学里，集合的元素不能重复；但在程序设计里，我们面对的往往是一个数组，比如 {1, 2, 2}，这个严格说应该叫做多重集合（multiset）。后面的推导对这两种情况都成立：只要把每个位置上的数当成一个独立个体去统计，公式就依然有效。真正需要小心的反而是负数、0 这些边界元素，我放到第 3、4 章分别讨论。

这两个问题在 {1,2,3} 上恰好都算出了 24，这是巧合，因为 1+2+3 和 1×2×3 都等于 6，而 6×4 和 2×3×4 也都等于 24。如果换成 {2,3,4}，和之和是 9×4=36，乘积之和是 3×4×5=60，两个答案就分道扬镳了。所以别看同一个例子结果相同就以为两个问题等价，它们的本质区别在通解里才真正显现。

2. 暴力枚举：先用最笨的办法拿到正确答案

在推导任何公式之前，先把暴力枚举写出来。这样做有两个目的：第一，小规模数据下暴力结果是绝对正确的，它可以作为后续公式的"对拍基准"；第二，暴力的复杂度能直观告诉你，为什么 n 稍微大一点就必须找通项。

暴力枚举子集的经典手段是二进制掩码。一个含有 n 个元素的集合，每个子集本质上就是在回答 n 个"选/不选"的问题，所以可以用一个 n 位的二进制数表示一个子集，掩码从 0 到 2ⁿ-1 走一遍，就恰好覆盖了所有子集。Python 代码如下：

def brute_sum_of_sums(arr): """所有子集的元素和 之和""" n = len(arr) total = 0 for mask in range(1 << n): s = 0 for i in range(n): if mask >> i & 1: s += arr[i] total += s return total def brute_sum_of_products(arr): """所有子集的元素乘积 之和""" n = len(arr) total = 0 for mask in range(1 << n): prod = 1 # 空集的乘积约定为 1 for i in range(n): if mask >> i & 1: prod *= arr[i] total += prod return total arr = [1, 2, 3] print(brute_sum_of_sums(arr)) # 24 print(brute_sum_of_products(arr)) # 24

这段代码结构很对称，唯一的差别是内层一个做加法、一个做乘法。运行起来会发现它极其慢：每个子集要花 O(n) 的时间去扫描哪些元素被选中了，所以整体复杂度是 O(n·2ⁿ)。n=20 时，2ⁿ 已经是一百多万，乘上 n 就是两千万次操作，Python 勉强能在一两秒内跑完；n=25 时直接变成几亿次操作，基本等不起；n=30 以上，哪怕换成 C++ 也完全不现实。

我在实际做题时很少真的用暴力去"算答案"，更多是用它做对拍。写出通项公式后，拿随机生成的小数组，让暴力结果和公式结果逐一比对，几十组数据全对上了，才敢把公式用到大数据上。这一步虽然简单，但能省掉大量因为想当然而导致的翻车。后面给出的两个公式，我建议你拿到手后也先写个对拍验证一下，体验会深刻很多。

3. 和之和的通解：关键在于"每个元素被数了多少次"

第一个问题的暴力算法慢，是因为它枚举的是"子集"。但是如果你换一个角度，不看子集、改看元素，问题会瞬间变得简单：所谓"所有子集的元素和之和"，本质上就是把每个元素在所有子集中的贡献累加起来。

具体来说，固定一个元素 a。它在多少个不同的子集里出现？答案是 2^(n-1) 个。理由很简单：包含 a 的子集，对于除了 a 以外的 n-1 个元素，每一个都有"选"和"不选"两种自由选择，所以总共有 2^(n-1) 种组合方式。这个计数和 a 本身是多少完全无关，纯粹由集合大小 n 决定。

于是求和顺序可以交换，把原来的"先枚举子集再枚举子集内元素"换成"先枚举元素再统计它出现在多少个子集里"：

Σ(所有子集的元素和) = Σ(每个元素 × 它出现的子集数) = (a₁ + a₂ + ... + aₙ) × 2^(n-1)

用刚才的 {1,2,3} 验证：元素和是 1+2+3=6，n-1=2，6×2²=24，和暴力结果一致。这个公式的形式非常漂亮：答案只取决于集合的总和与集合大小，和每个元素的具体数值分布完全无关。

这个推导过程在组合计数里有个专门的说法，叫"贡献法"或者"交换求和顺序"。它的核心思想是：当直接枚举对象太复杂时，把统计维度切换一下。这里切换的方式极其自然——每个子集的元素和是一堆数的加法，加法本来就可以随意交换顺序，那么所有子集放在一起看，每个元素被加了多少次就是个纯粹的计数问题。

这个公式对负数和 0 也完全成立。0 元素的贡献是 0×2^(n-1)=0，加不加上它都不影响结果；负数则照常参与求和与乘法，贡献可能是负的。这也带来一个实际提醒：如果在程序里用公式计算，千万不要先把数组元素逐个取模再求和，因为取模之后再乘 2 的幂，和直接计算再取模在数学上虽然等价，但中间步骤可能因为负数产生混淆，最好统一转成正数再处理，这部分我在第 6 章再展开。

还有一个很容易忽略的细节：如果集合里有重复元素，比如数组 {1, 2, 2}，这个公式依然成立吗？成立。因为程序里的数组天然把每个位置当成独立个体，两个 2 是"不同的元素"，各自都出现在 2^(3-1)=4 个子集中，公式会正确地统计两次。但如果按数学集合的概念去重后的 {1,2}，那就要按 n=2 重算。所以拿到题目一定要先确认它给的是数组还是真正的集合，这直接决定 n 是多少。

4. 乘积之和的通解：原来是在展开(1+a₁)(1+a₂)…(1+aₙ)

第二个问题就没那么直观了，因为"乘积"的选择并不是简单的线性叠加。刚接触这个问题的时候，我下意识觉得它可能和第一个问题类似，答案也许是"所有元素乘积 × 2^(n-1)"，但一验算就发现不对：{1,2,3} 的元素乘积是 6，6×4=24，居然碰巧对上了，换成 {2,3,4} 立刻露馅——元素乘积是 24，24×4=96，而真正的答案 3×4×5=60，差了十万八千里。所以必须老老实实重新推导。

回到二进制的视角。一个子集对应一串"选/不选"的决策：对于元素 a₁，选它就在乘积里乘一个 a₁，不选它就不乘；不乘这个动作，数学上等价于乘一个 1。所以每一个子集的乘积可以写成：

每个子集对应一个式子 = ∏(当前元素如果被选中就取 aᵢ，否则取 1)

把所有子集对应的式子的结果全部加起来，恰好就是下面这个连乘展开的每一项：

(1 + a₁)(1 + a₂) ... (1 + aₙ)

为什么？因为你在展开这个多项式的时候，每个括号里要么选 1、要么选 aᵢ，把所有可能的选法展开相加，每一种选法就对应一个子集，展开后的每一项就是那个子集的元素乘积。所以：

Σ(所有子集的元素乘积) = ∏(1 + aᵢ) = (1+a₁)(1+a₂)...(1+aₙ)

这就是问题的通解。用 {1,2,3} 验证：(1+1)(1+2)(1+3) = 2×3×4 = 24，和暴力结果一致。

这个结论同时解释了我前面所说的约定：空集的乘积为什么要按 1 算？因为空集对应所有括号都选 1 的情况，展开后这一项就是 1×1×...×1=1。如果你把空集的乘积按 0 算，展开式的第一项就是 0，整个公式就得额外减掉 1 再补上 0 的规定，公式就变得丑陋了。乘法单位元是 1，这个约定不是刻意为之，是从"不选就等价于乘 1"这个事实里自然长出来的。

这个公式的另一个理解方式是把它看成乘法分配律的推广。中学学过的 (a+b)(c+d) 就是两个集合的"选/不选"展开，只是中学只让你展开两个括号，而现在展开 n 个括号，每一个括号代表一个元素的两种选择。这种视角在组合数学里非常常见——很多看起来要枚举 2ⁿ 个子集的问题，其实只是一个多项式展开的某个系数或者某个特殊取值。

公式还对 0 元素非常宽容：如果某个 aᵢ = 0，对应的括号是 (1+0)=1，对结果毫无影响。但如果集合里有 -1，对应括号就是 (1-1)=0，整个乘积直接归零。这个现象从子集角度看也很直观：任何包含 -1 的子集和任何不包含 -1 的子集，两部分贡献刚好正负抵消。处理负数元素时，这个性质经常会导致"一眼看上去应该很大的答案，结果却是 0"的意外。

5. 用生成函数把两个问题放进同一个框架

两个公式单独看都挺简洁，但放在一起总觉得差点意思：一个带 2 的幂，一个是连乘展开，它们真的是同一个问题家族里的兄弟吗？答案是肯定的，把它们统一起来的工具是生成函数。

考虑多项式 F(x) = ∏(1 + x^{aᵢ})，这里 x 的指数就是子集的元素和。展开这个多项式，每一项 x 的指数恰好等于某个子集的元素和，前面的系数是这个元素和出现的次数。把 F(x) 在 x=1 处取值，得到的是所有子集的总个数 2ⁿ；对 F(x) 求导再代入 x=1，得到的正是所有子集的元素和之和——因为每一项 x^k 求导后变成 k·x^(k-1)，代入 x=1 就是 k。

再看第二个问题，引入另一个多项式 G(x) = ∏(1 + aᵢ x)，这次 x 的指数是子集的大小，前面的系数是子集的元素乘积。展开后每一项的系数就是"大小为 k 的子集的乘积之和"，把 x=1 代进去，所有子集的乘积之和就自然出现了。这两个多项式唯一的区别是 x 的位置：F 把 x 放在指数上记录"和"，G 把 x 放在系数上记录"乘积"。这个对比恰好反映了两个问题本质上的不同——第一个问题是线性求和，适合用导数提取；第二个问题是乘积结构，适合用代值提取。

顺带说一句，G(x) 展开后的系数在数学里有一个正式名字，叫做初等对称多项式 e_k。e₀=1，e₁=a₁+...+aₙ，e₂=∑_{i<j}aᵢaⱼ，以此类推。G(x) = Σ e_k x^k，所以在 x=1 取值得到的 Σe_k，本质上就是所有初等对称多项式之和。了解了这个背景，很多变体题就有了统一解法：如果题目要求"只取大小为 k 的子集"的乘积之和，那答案就是 e_k，直接用动态规划维护 G(x) 的系数，复杂度 O(n²)，这是背包思想在组合计数里的经典应用。

生成函数的意义不在于让你背下几个公式，而在于它提供了一个"翻译器"：把集合运算翻译成多项式运算，把计数问题翻译成系数提取问题。很多看起来需要枚举 2ⁿ 种情况的题目，翻译之后都能用求导、代值、提取系数等手段在多项式时间内解决。你掌握的翻译模式越多，遇到新题时能走的捷径就越多。

6. 实战环节：大数、负数、取模与常见变体

前面推导的都是精确数学公式，但真到写代码的时候，第一个拦路虎就是整数溢出。n 稍微大一点，2^(n-1) 和 ∏(1+aᵢ) 都会爆炸式增长，所以竞赛和面试题里几乎都会要求对某个模数取余，最常见的是 10⁹+7。这个模数是质数，而且和 2 互质，用快速幂算 2 的幂非常方便。下面给出两个公式的取模实现：

MOD = 10**9 + 7 def subset_sum_total(arr): """所有子集元素和之和，对 MOD 取模""" n = len(arr) total = sum(arr) % MOD return total * pow(2, n - 1, MOD) % MOD def subset_product_total(arr): """所有子集元素乘积之和，对 MOD 取模""" ans = 1 for a in arr: ans = ans * ((1 + a) % MOD) % MOD return ans

这里有一个特别容易出错的细节：第二个公式里 (1 + a) 必须先处理负数和超大数。如果 a 是负数，比如 -5，在 Python 里 (-5) % MOD 得到的是 MOD-5，这是正确的非负余数，然后再加 1 取模就稳妥了。如果 a 刚好等于 MOD-1，那么 (1+a) % MOD 等于 0，整个乘积会直接变成 0，这是正常的数学结果，但有些人会怀疑是不是代码写错了——其实不是，因为这等价于集合里有一个元素等于 -1 的情况，对应括号的值恰好是 0。

除了精度问题，这两个公式在算法题里最常见的几个变体也值得记一下。一个是"所有子集的异或和"，它和第一个问题同宗同源，用的是按位贡献法：单独看某一位，如果这一位在所有元素中至少出现过一次，那么在所有子集里这一位为 1 的子集数恰好是 2^(n-1)；如果从未出现过，贡献为 0。所以答案等于 2^(n-1) 乘以全部元素按位或的结果。LeetCode 1863 题本质就是这个模型。代码很简洁：

def subset_xor_total(arr): """所有子集异或和之和""" bit_or = 0 for a in arr: bit_or |= a return bit_or * (1 << (len(arr) - 1))

另一个变体是"所有大小为 k 的子集的乘积之和"，也就是求初等对称多项式 e_k。这个用动态规划维护多项式系数：dp[j] 表示当前已经处理了若干元素后，大小为 j 的子集乘积之和，每来一个新元素 a，就有两种选择——不选它，dp 保持不变；选它，所有大小为 j-1 的子集都要乘上 a 并变成大小为 j 的子集。转移方程是 dp[j] = dp[j] + dp[j-1]×a，从大到小更新避免覆盖。这样一来 O(nk) 就能求出结果，而不是枚举所有组合。

这些变体背后其实都在反复用一个套路：交换求和顺序，用贡献法把"枚举子集"换成"统计元素/位/维度被选中的次数"。第一个问题里，每个元素被选中 2^(n-1) 次；异或和问题里，每一位被选中 2^(n-1) 次；乘积之和问题里，每个元素提供 (1+aᵢ) 这个因子。一旦你看穿了这一点，很多子集计数题其实都是同一道题换了层皮。

回到最初的两个问题，我在实际过程中最大的体会是：拿到一个"求所有子集某种属性之和"的题目，第一反应不要是去枚举子集，而是先问自己——能不能把求和顺序换一下？交换求和顺序之后，原来的对象复杂度瞬间从 2ⁿ 降到多项式级别，剩下的事情往往就是数数。这比记住任何具体公式都重要，因为公式会变，但"换个维度统计"这个思路能覆盖的问题范围要宽广得多。