SOSDP ( Sum Over Subsets Dynamic Programming)，中文名子集 DP。
下面给一个最 Common 的用法：
给定一个集合 \(S = \{a_0, a_1, \dots , a_{n - 1}\}\)，求：
\[\sum_{T \subseteq S} \sum_{a_i \in T} a_i
\]
即 \(S\) 的子集和。
暴力做是 \(\mathcal O(3^n)\) 的，而用 SOSDP 可以把时间复杂度降至 \(\mathcal O(n2^n)\)。
\(\mathcal O(3^n)\)：
for (int S = 0; S < (1 << n); S++) {
for (int T = S; T; T -= (T & -T)) sum += a[__builtin_ctz(T)];
}
\(\mathcal O(n2^n)\)：
for (int i = 0; i < n; i++) {
for (int S = 0; S < (1 << n); S++) if (S & (1 << i)) sum += a[i];
}
核心思想是从枚举子集再枚举子集内的元素求和转化为枚举每个元素并统计其对某些子集的贡献。