Meet in the Middle

Split items into halves, enumerate all sums per half, then combine with sorting + two pointers or hash map.

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

• Halving reduces 2^n to about 2 * 2^(n/2) work for combine step.
• Watch memory when enumerating both halves fully.
• Sort one list for binary search merges.