Compute sums of all subsets of some words
If you think that there are much fewer than $2^{16} $ sums, you can try the following approach. Iteratively compute a sorted list of all partial sums of the first $k$ values.  Given this list for some $k$, add to all sums in the list $W_{k+1} $, and then merge the two lists like in Mergesort, removing duplicates. The total complexity should be asymptotic to the number of distinct partial sums.