1272. Adding Up Every Subset Total at Once

A value f[S] is given for every one of the 2^n subsets S of n items, indexed by mask. For EVERY mask m, compute

g[m] = sum of f[s] over all submasks s of m

and print all 2^n results in mask order.

n=2, f = 1 2 3 4 -> 1 3 4 10 because g[0]=f[0]=1, g[1]=f[0]+f[1]=3, g[2]=f[0]+f[2]=4 and g[3]=f[0]+f[1]+f[2]+f[3]=10`.

## What most people try first

Enumerate the submasks of each mask with #1270's loop and add them up. That is correct and, by #1271's count, it is exactly 3^n additions. At n = 16 that is 43046721, which is fine. At n = 20 it is 3486784401, which is not.

The better method is not an optimisation of that loop. It replaces it.

## Peel one position at a time

Think of g[m] as built in n LAYERS, where after layer b the array holds

h_b[m] = sum of f[s] over the s that agree with m on positions b, b+1, ... and are free below position b

Start with h_0 = f, where nothing is free and each entry is just f[m]. To go from layer b to layer b+1, position b becomes free. If m does not have bit b, then a submask cannot have it either, so nothing changes. If m does have bit b, the submasks split into those that include it and those that do not, and those two groups are exactly h_b[m] and h_b[m without bit b]:

for b in 0 .. n-1: for m in 0 .. 2^n - 1: if m has bit b: g[m] += g[m without bit b]

After all n layers every position is free, which is precisely the condition "s is a submask of m", so the array holds g.

## Why it is correct and not double counting

Each submask s of m is added to g[m] along exactly one route: the positions where s and m differ are, by definition, positions m has and s does not, and each such position contributes its halving at its own layer, once. There is no order in which a position can be used twice, because the layer loop visits each position once.

The inner loop may be taken in any mask order, because layer b only ever reads m without bit b, which is a DIFFERENT mask whose layer-b value was already correct before the layer started and is not modified by this layer (it has no bit b). That is worth checking rather than assuming; it is why no second array is needed.

## Cost

O(n * 2^n) additions: 1048576 at n = 16 and 20971520 at n = 20, against 3^n's 3486784401. The technique is usually called the sum over subsets transform, or the zeta transform, and it is the subset analogue of a prefix sum: #1273 is the other direction and #721's prefix array is the same idea on a line.

## Width

Masks are below 2^16 = 65536, so all the index arithmetic fits in a signed 32-bit integer and JavaScript's &, | and ^ are safe on plain Numbers.

The VALUES are not narrow. Each f[S] can be 10^9, and g[m] sums up to 2^16 = 65536 of them, reaching about 6.5 * 10^13. That is past the 2147483647 a signed 32-bit integer holds by four orders of magnitude, so the array must hold 64-bit values. Note 2 * 10^9 would still fit in 32 bits; it is the accumulation that does not. In JavaScript 6.5 * 10^13 is below 2^53 = 9007199254740992, so a plain Number array stays exact and BigInt is not needed.

Constraints - `0 ≤ n ≤ 16` - `0 ≤ f[S] ≤ 1000000000`