Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
For every mask, you want F[mask] = sum of A[s] over all submasks s of mask. Enumerating submasks directly is O(3ⁿ). Sum Over Subsets DP does it in O(2ⁿ · n): process one bit i at a time, and for every mask that has bit i set, add in F[mask without bit i]. After all n bits, each F[mask] holds the full subset sum. It's a dimension-by-dimension prefix sum over the Boolean hypercube.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can turn an O(3ⁿ) submask enumeration into O(2ⁿ · n) by recognizing subset-sum as a prefix sum along each bit dimension, and order the loops correctly.
Where candidates slip
Swapping the loop nesting (masks outside, bits inside) or double-counting by reading already-updated entries, both of which corrupt the dimension-by-dimension invariant.
How to stand out
Frame SOS as a hypercube prefix sum, state the per-bit invariant precisely, and contrast it with the naive O(3ⁿ) submask loop.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewSubset sum for every maskNeed all masks at once?One maskAll masksExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Naive Submask Enumeration
1Hint 1Explore hintHide hint
For a single mask m, how do you iterate exactly its submasks without touching non-submasks?
2Hint 2Explore hintHide hint
Use the idiom sub = (sub - 1) & m starting from sub = m, stopping after processing sub = 0. It visits every submask once.
3Hint 3Explore hintHide hint
Wrap that submask walk inside a loop over all masks m. Summing over all m, the total submask count is 3ⁿ.
A · Core idea
Compute each F[m] independently by visiting only the submasks of m.
The submask idiom. Given a mask m, the loop sub = m; sub = (sub - 1) & m enumerates every submask in strictly decreasing order, ending at 0. The & m step keeps you inside m's bits; subtracting 1 borrows through the lowest set bit just like ordinary binary counting confined to the mask.
Accumulate. For each m, sum A[sub] over all its submasks into F[m]. Handle sub = 0 explicitly so the loop terminates after processing the empty submask.
Why the cost is 3ⁿ, not 4ⁿ. For each of the n bits, a (mask, submask) pair is in one of three states: the bit is in neither, in the mask only, or in both. That's 3 choices per bit, hence 3ⁿ total pairs — the exact number of submask visits.
Why we improve it. 3ⁿ is far worse than 2ⁿ. At n = 20 it's ~3.5 billion versus the SOS DP's ~21 million. The naive version re-derives shared sub-sums for many masks; SOS DP shares them.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 2, A = [3, 1, 4, 2]Array state
m=00,01
3, 4
[3, 4, 7, 10]C · Code with teaching comments
Reference implementation previewpublic long[] sumOverSubsets(int n, long[] A) { int size = 1 << n; long[] F = new long[size]; for (int m = 0; m < size; m++) { int sub = m;Explore the full codeHide the full code
D · Why it works and complexityO(3ⁿ) timeO(2ⁿ) spaceOpen the invariant and proofExplore the proofHide the proof
The submask idiom (sub - 1) & m is the canonical way to walk subsets of a mask, but doing it per mask recomputes overlapping work. The leap is realizing those overlaps form a prefix-sum structure along each bit axis.
ComplexityO(3ⁿ) time, O(2ⁿ) space — Across all masks, the number of (mask, submask) pairs is Σ 2^popcount(m) = 3ⁿ (each bit is independently absent, present-in-both, or present-only-in-m). So O(3ⁿ) time; F is O(2ⁿ) space.
E · Edge cases and pitfalls3Omitting the sub == 0 break — the loop never terminates.Explore edge casesHide edge cases
Pitfalls
- Omitting the sub == 0 break — the loop never terminates.
- Forgetting & m, so the walk leaves m's bits and adds wrong entries.
- Treating O(3ⁿ) as acceptable at large n — it blows up fast.
Approach 2 of 2 · Optimal
Sum Over Subsets DP — Bit by Bit (Optimal)
1Hint 1Explore hintHide hint
Picture masks as corners of an n-D cube. A 1-D prefix sum sweeps one axis; how would you prefix-sum along every bit axis in turn?
2Hint 2Explore hintHide hint
Process bits one at a time. After handling bit i, F[mask] should equal the sum of A over submasks that agree with mask on bits above i and are ≤ mask on bits 0..i.
3Hint 3Explore hintHide hint
For each bit i, for every mask with bit i set, do F[mask] += F[mask ^ (1<<i)]. The cleared-bit entry already holds the partial sum from earlier bits — that's why the loop order matters.
A · Core idea
Treat the subset sum as a prefix sum performed independently along each of the n bit dimensions.
The hypercube view. Index masks as 0/1 vectors of length n — the corners of an n-dimensional cube. F[m] sums A over every corner componentwise ≤ m (every submask). A classic n-dimensional prefix sum computes exactly this if you prefix-sum along one axis at a time; SOS DP is that idea applied to the Boolean cube.
The per-bit relaxation. Start with F = A. For bit i from 0 to n - 1, scan every mask. If mask has bit i set, add F[mask ^ (1 << i)] into F[mask]. In words: a mask that includes element i absorbs the accumulated value of the otherwise-identical mask that excludes i.
The invariant that makes it correct. After processing bits 0..i, F[mask] holds the sum of A[s] over all submasks s that match mask exactly on bits > i and may differ freely on bits 0..i. Each new bit i extends the freedom by one dimension. After the last bit, mask may differ on all bits below it — i.e. F[mask] is the sum over all submasks.
Why the loop order is non-negotiable. When you process bit i, the entry F[mask ^ (1 << i)] must already reflect bits 0..i-1 but not bit i. Because bit i is clear in mask ^ (1 << i), this round leaves it untouched, so reading it is safe and adds no double-count. Swapping the loops (masks outside, bits inside) destroys this staging and produces wrong sums.
Superset variant. To sum over supersets instead, keep the same skeleton but update the cleared-bit entry from the set-bit one: F[mask ^ (1 << i)] += F[mask]. Same O(2ⁿ · n) cost, opposite direction on the lattice.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 2, A = [3, 1, 4, 2]Array state
init
F = A
[3, 4, 7, 10]C · Code with teaching comments
D · Why it works and complexityO(2ⁿ · n) timeO(2ⁿ) spaceOpen the invariant and proofExplore the proofHide the proof
SOS DP is the subset-lattice analogue of a 2-D prefix sum done row-sweep then column-sweep. Each bit is an axis; relaxing it once accumulates that axis. Because the axes are independent, n single-axis sweeps compose into the full subset sum — turning 3ⁿ overlapping walks into 2ⁿ · n disjoint updates.
ComplexityO(2ⁿ · n) time, O(2ⁿ) space — Two nested loops: n bits times 2ⁿ masks, with O(1) work each — O(2ⁿ · n). The DP runs in place on F (a copy of A), so space is O(2ⁿ).
E · Edge cases and pitfalls7n = 1, A = [5, 2] — Only bit 0; F[1] += F[0] → [5, 7].Explore edge casesHide edge cases
Edge cases handled
n = 1, A = [5, 2]Only bit 0; F[1] += F[0] → [5, 7].all zeros AEvery F[mask] stays 0; sums of zeros.single nonzero at full maskA[2ⁿ-1]=v has no proper supermask, so only F[2ⁿ-1]=v changes.n = 20~21M updates; use 64-bit accumulators to avoid overflow on large value sums.
Pitfalls
- Swapping the loop order (masks outside, bits inside) — breaks the per-bit staging invariant.
- Updating masks where bit i is clear, or reading F[mask | (1<<i)] — both double-count.
- Using 32-bit ints when many values sum into one mask — overflow.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long[] sumOverSubsets(int n, long[] A) { int size = 1 << n; long[] F = A.clone(); for (int i = 0; i < n; i++) { for (int mask = 0; mask < size; mask++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Loop order swapped
If masks are the outer loop and bits the inner, F[mask ^ (1<<i)] may already include bit i's contribution from a later bit's pass, double-counting and corrupting sums.
Explore the code comparisonHide the code comparison
Loop order swapped
If masks are the outer loop and bits the inner, F[mask ^ (1<<i)] may already include bit i's contribution from a later bit's pass, double-counting and corrupting sums.
Don't write this
for mask in range(size): # WRONG outer
for i in range(n):
if mask & (1 << i):
F[mask] += F[mask ^ (1 << i)]Write this instead
for i in range(n): # bits outer
for mask in range(size):
if mask & (1 << i):
F[mask] += F[mask ^ (1 << i)]2Wrong neighbor read
Reading the supermask F[mask | (1<<i)] instead of the cleared-bit submask F[mask ^ (1<<i)] computes a different (and inconsistent) quantity, not the subset sum.
Explore the code comparisonHide the code comparison
Wrong neighbor read
Reading the supermask F[mask | (1<<i)] instead of the cleared-bit submask F[mask ^ (1<<i)] computes a different (and inconsistent) quantity, not the subset sum.
Don't write this
if ((mask & (1 << i)) != 0) {
F[mask] += F[mask | (1 << i)]; // same as mask — adds itself
}Write this instead
if ((mask & (1 << i)) != 0) {
F[mask] += F[mask ^ (1 << i)]; // clear bit i, read the submask
}Revise
Carry the pattern into the interview
Pattern to remember
SOS DP — accumulate one bit dimension at a time over the hypercube
Code pattern to memorize
F = A.copy()
for i in 0 .. n-1:
for mask in 0 .. 2^n - 1:
if mask & (1 << i):
F[mask] += F[mask ^ (1 << i)]
# F[mask] = sum of A[s] over all submasks s ⊆ maskRules to remember
- 1Initialize
F = A(each mask starts holding only its own value). - 2Outer loop over bits i, inner loop over masks — never swap the nesting.
- 3Only update masks where bit i is set; add the value of the mask with bit i cleared.
- 4After bit i,
F[mask]holds the sum over submasks that may differ frommaskonly in bits0..i. - 5It's a 2ⁿ × n in-place DP; for superset sums flip the update to
F[mask without bit i] += F[mask].
Use this pattern when
- You need subset-sum (or subset-aggregate) for every mask at once
- Counting pairs / triples by subset or superset containment over bitmasks
- Convolutions over the subset lattice (AND/OR convolution building blocks)
- Replacing an O(3ⁿ) submask loop with O(2ⁿ · n)
Choose another pattern when
- You need only one mask's subset sum → a single O(2^popcount) submask walk is enough
- n is large (≥ ~22) → 2ⁿ memory is infeasible regardless
- The aggregate isn't decomposable bit-by-bit (e.g. depends on order) → SOS doesn't apply
- Plain prefix sums on an array → standard 1-D prefix, not hypercube DP
Interview takeaway
SOS DP is a multidimensional prefix sum on the n-bit hypercube: relax one bit at a time and each mask absorbs its submasks in O(2ⁿ · n). Once you see subsets as points in a Boolean cube, the bit-by-bit relaxation is just prefix-summing along each axis.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternSOS DP is a multidimensional prefix sum on the n-bit hypercube: relax one bit dimension per outer pass to turn an O(3ⁿ) submask enumeration into O(2ⁿ · n). The same skeleton, reversed, sums over supersets and underlies subset/superset convolutions.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- The Number of Good SubsetsComing soonMask DP over prime-factor sets; SOS-style aggregation counts compatible subsets.
- Maximum Score WordsComing soonBitmask DP over letter usage — same hypercube state space, different transition.
- Subset Superset CountingComing soonFlip the SOS update direction to aggregate over supersets in the same O(2ⁿ · n).
- Maximum Students Taking ExamComing soonProfile bitmask DP; SOS techniques speed up transitions over compatible row masks.