Somme distinte di sottoinsiemi con meet-in-the-middle

Dato l'insieme $S = \{3, 7, 12, 18, 25, 31, 44, 52\}$, considera le somme di tutti i suoi 256 sottoinsiemi (il sottoinsieme vuoto ha somma 0). Quanti valori distinti compaiono tra queste somme? (Tecnica suggerita: meet-in-the-middle sulle due metà $\{3, 7, 12, 18\}$ e $\{25, 31, 44, 52\}$.)