SOS DP
Transform subset-based values so every mask can aggregate information from all of its submasks or supermasks efficiently.
SOS DP
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
SOS DP means ``sum over subsets'' DP, but the idea is broader than just sums. It is the standard transform when each mask needs information from all of its submasks or all of its supermasks, and the naive \(O(4^n)\) approach is too slow.
When to Use It
Use SOS DP when:
the state is a bitmask,
each mask wants to aggregate values over all submasks or all supermasks,
\(n\) is small enough for \(2^n\) states but not small enough for nested subset enumeration on every mask.
Core Idea
Instead of iterating through every \((mask, submask)\) pair independently, process the bits one by one. At each bit, decide whether information should flow from the version without that bit to the version with that bit.
That transforms the brute-force subset aggregation into a dimension-by-dimension DP over the hypercube.
Key Insight
The expensive part is repeated reuse of the same smaller masks. SOS DP avoids recomputing that reuse from scratch. It folds one bit at a time, very much like a fast transform.
Operations / Main Technique
initialize \(\texttt{f[mask]}\) with the base values,
for each bit, propagate from masks missing that bit to masks containing it,
read the transformed array as ``sum over all submasks'' or the corresponding variant.
Worked example.
If \(\texttt{f[mask]}\) counts exact masks, the transformed array after SOS can store how many exact masks are subsets of each query mask. That is the version used in many inclusion-style bitmask problems.
Correctness Intuition
After processing the first \(b\) bits, each state already contains the aggregate over all choices of those bits that are compatible with it. When the next bit is processed, the same invariant extends by one dimension. After all bits are processed, every submask has been accounted for exactly once.
Complexity Analysis
For \(n\) bits:
time: \(O(n 2^n)\),
memory: \(O(2^n)\).
Implementation
The code includes both:
subset-sum transform,
superset-sum transform.
That is the pair I reach for most often.
Common Pitfalls
Using SOS DP when ordinary submask enumeration is already fast enough.
Mixing up the subset and superset directions.
Forgetting that the state count still grows as \(2^n\), so the bit count must stay small.
Variants / Extensions
Fast zeta transform and Mobius inversion on subsets.
XOR / AND / OR convolution families.
Bitset tricks when the values are boolean instead of numeric counts.
Practice Problems
Count how many given masks are subsets of each query mask.
Optimize over all supermasks of a state.
Inclusion-style DP where many masks share the same submask contributions.
References
Code
Contest-ready reference implementation for the idea explained above.
vector<long long> sos_subsets(vector<long long> f, int bits) {
for (int bit = 0; bit < bits; ++bit) {
for (int mask = 0; mask < (1 << bits); ++mask) {
if ((mask >> bit) & 1) {
f[mask] += f[mask ^ (1 << bit)];
}
}
}
return f;
}
vector<long long> sos_supersets(vector<long long> f, int bits) {
for (int bit = 0; bit < bits; ++bit) {
for (int mask = 0; mask < (1 << bits); ++mask) {
if (((mask >> bit) & 1) == 0) {
f[mask] += f[mask | (1 << bit)];
}
}
}
return f;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.