Sum over subsets
You are given an integer n (number of bits) and an array a of length 2**n. For every mask m in [0, 2**n), 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 2**n. Constraints: 1 <= n <= 12, so the array fits and the classic O(n * 2**n) sum-over-subsets DP is required (a naive O(3**n) submask enumeration is too slow at the top range).
Implement
sum_over_subsets(n: int, a: list[int]) → list[int]Examples
in
[2,[1,2,3,4]]out[1,3,4,10]What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 35 min
solution.py
InputExpectedGot
[2,[1,2,3,4]][1,3,4,10]not run yetsample