1401. SOS DP — Sum Over Subsets Using Bitmask

You are given a function f defined on all 2^n subset bitmasks, provided as an array of length 2^n where f[mask] is the value at that mask. Compute F[mask] equal to the sum of f[s] over every submask s of mask, and return the whole array F of length 2^n.

Input: A JSON object {"n": <bit count>, "f": [<2^n values indexed by mask>]}.

Output: Return the array F where F[mask] sums f over all submasks of mask.

Examples

Input: {"n":2,"f":[1,2,3,4]}
Output: [1,3,4,10]
Explanation: Each F[mask] sums f over its submasks -> [1,3,4,10].

Input: {"n":1,"f":[5,7]}
Output: [5,12]
Explanation: F[0]=5 and F[1]=5+7=12 -> [5,12].

Constraints

• 0 <= n <= 16
• 0 <= f[mask] <= 10^6

Asked by