Meet in the middle

இரண்டு பாதி; sums enumerate; merge.

Try this in Python

def subset_sums(arr: list[int]) -> list[int]:
    out = []
    n = len(arr)
    for mask in range(1 << n):
        s = 0
        for i in range(n):
            if (mask >> i) & 1:
                s += arr[i]
        out.append(s)
    return sorted(out)


a = [1, 2, 4]
print(subset_sums(a)[:8])

Key takeaways

• 2^n → 2*2^(n/2).
• Memory.
• Sort + bisect.