Overview
Given an array `A`, you want `F[mask] = SUM(A[i])` for all `i` that are subsets of `mask`. A naive loop over all submasks takes O(3^N).
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
Efficiently compute the sum of all subsets of a given bitmask for all masks. SOS DP optimizes the naive O(3^N) approach to O(N * 2^N).
Given an array `A`, you want `F[mask] = SUM(A[i])` for all `i` that are subsets of `mask`. A naive loop over all submasks takes O(3^N).
Instead of iterating all submasks at once, we add them dimension by dimension (bit by bit). This is essentially a multi-dimensional prefix sum over a hypercube.
The outer loop iterates over the bit index `i` (0 to N-1). The inner loop iterates over all masks. If the `i`-th bit is ON in the mask, we add the value of the mask where that bit is OFF.
By the time we process bit `i`, `dp[mask]` already contains the sum of subsets differing in bits `0` to `i-1`. Adding `dp[mask ^ (1 << i)]` safely folds in the subsets that differ at bit `i`.