The problem

Let \([n]\) denote the set \(\set{1, 2, \dots, n}\). Given is a function \(f\colon 2^{[n]} \to \R\). Define function \(F\colon 2^{[n]} \to \R\), \(F(S) := \sum_{T \sse S} f(T)\). Find the value of \(F(S)\) for each subset \(S\) of \([n]\).

The \(O(3^n)\)-time algorithm

for (int s = 0; s < 1 << n; s++) {
    F[s] = f[0];
    // iterate over nonempty subsets of s
    for (int t = s; t > 0; t = (t - 1) & s) {
        f[s] += f[t];
    }
}

The \(O(n2^n)\)-time algorithm

For a subset \(S\) of \([n]\), let’s group subsets of \(S\) in the following way. For each \(i = 0, 1, \dots, n\), let \(G(S, i)\) be the set of subsets of \(S\) such that, for each subset \(T \in G(S, i)\) and for each integer \(j \in [i + 1, n]\), \(j \in S \implies j \in T\). In other words, each subset \(T \in G(S, i)\) differs from \(S\) only in integers not greater than \(i\). The following recurrence relation for \(G(S, i)\) holds \[ \begin{equation} G(S, i) = \begin{cases} G(S, i - 1), & \text{if $i \not \in S$} \\ G(S, i - 1) \sqcup G(S \setminus i, i), & \text{if $i \in S$} \end{cases} \label{Rec:1} \end{equation} \] where the symbol \(\sqcup\) stands for disjoint set union. Note that the second equation of \(\eqref{Rec:1}\) can also be written as \[ G(S, i) = G(S, i - 1) \sqcup G(S \setminus i, i - 1), \quad \text{if $i \in S$}. \]

The following code follows easily from \(\eqref{Rec:1}\)

for (int s = 0; s < 1 << n; s++)
    F[s] = f[s];

for (int i = 0; i < n; i++)
  for (int s = 0; s < 1 << n; s++)
    if (s >> i & 1)
      F[s] += F[s ^ (1 << i)];

References

• https://codeforces.com/blog/entry/45223