Senior LevelData Structures & Algorithms
What is Sum over Subsets (SOS) Dynamic Programming?
ā Interview Prompt: Explain SOS DP for computing subset sum/max over all subsets of a bitmask in O(N Ć 2^N) instead of O(3^N) brute force.
Sum over Subsets (SOS) DP computes for each mask $S$:
$$F[S] = \sum_{T \subseteq S} A[T]$$
in $O(N \times 2^N)$ instead of naively iterating all subsets of $S$ ($O(3^N)$ total).
Algorithm (Zeta Transform):
```
for bit in 0..N-1:
for mask in 0..2^N-1:
if mask has bit set:
F[mask] += F[mask ^ (1 << bit)]
```
After $N$ passes, $F[S]$ = sum of $A[T]$ over all subsets $T$ of $S$.
Applications:
ā¢
Counting set bits in subsets.
ā¢
AND/OR convolution.
ā¢
Profile DP on broken profiles.
Code Implementation Example
typescript
// SOS DP ā Sum over Subsets in O(N Ć 2^N)
function sosDP(A: number[], N: number): number[] {
const F = [...A]; // copy; F[S] will hold sum over all subsets of S
for (let bit = 0; bit < N; bit++) {
for (let mask = 0; mask < (1 << N); mask++) {
if (mask & (1 << bit)) {
F[mask] += F[mask ^ (1 << bit)]; // add contribution of subsets without this bit
}
}
}
return F;
}
// Example: A = [0, 1, 2, 3] (values indexed by 2-bit masks)
// F[3] = A[0] + A[1] + A[2] + A[3] = 6 (sum over all subsets of {0,1})
const result = sosDP([0, 1, 2, 3], 2);
console.log(result); // [0, 1, 2, 6]š”SOS DP computing subset sums for all masks in O(N Ć 2^N) using dimension-wise accumulation.
šÆ Interview Key Takeaway
SOS DP is the standard O(N Ć 2^N) technique for subset sum/max queries. Essential in competitive programming for AND/OR convolution and profile DP problems.
#DSA#SOS DP#Bitmask#Subset Sum#Senior
Back to all Data Structures & Algorithms Questionsā