Sum over subsets
Your task
You are given an integer n (number of bits) and an array a of length 2n. For every mask m in [0, 2n), compute f(m) = the sum of a[s] over all submasks s of m (i.e. s & m == s). Return the resulting array f of length 2n. Constraints: 1 <= n <= 12, so the array fits and the classic O(n * 2n) sum-over-subsets DP is required (a naive O(3**n) submask enumeration is too slow at the top range).
Examples
sum_over_subsets(n: int, a: list[int]) -> list[int]Example 1
Input
sum_over_subsets(2, [1, 2, 3, 4])Output
[1, 3, 4, 10]