How Many Distinct Subset Totals
Count the DISTINCT values that arise as the total of some subset, including the empty subset whose total is 0.
1 2 3 -> 7 0 1 2 3 4 5 6
1 1 1 -> 4 0 1 2 3
2 4 8 -> 8 every subset gives a different total
The contrast between the first two lines is the whole problem. Both have three elements and eight subsets, and one produces seven distinct totals and the other four. The answer depends on collisions, so the totals have to be collected rather than counted.
## Reachability, then a count
This is not a counting DP in the sense of problem 483, which counts subsets per total. Here each total is worth 1 no matter how many subsets produce it, so the table is BOOLEAN and the answer is how many entries are set.
reach[0] = true
for each value v:
for t from S down to v:
reach[t] = reach[t] or reach[t - v]
answer = number of true entries
where S is the sum of all values.
Replacing an addition by an OR is what turns "how many subsets reach each total" into
"which totals are reachable", and the difference in the final answer is the difference
between 8 subsets and 4 totals on 1 1 1.
## The loop direction
Downward, as always for at-most-once. Upward would let a value be reused, which makes
1 alone report every total up to S rather than just 0 and 1.
## Zeros
A value of 0 adds no new total, so it contributes nothing. 0 answers 1 and 0 0
answers 1: the only reachable total is 0.
The general loop handles it, since reach[t] or reach[t-0] is reach[t], but only if
the loop bound is written as t >= v rather than t > v. It is one of the few places
where a zero value is completely inert rather than doubling something.
## The bitset speed-up worth knowing
The inner loop is a shift and an OR over a bit array, so the whole thing can be written as
reach = reach | (reach << v)
on a bitset, which processes 64 totals per machine word and is roughly 64 times faster.
Python integers do this natively with | and <<, C++ has std::bitset, and Java has
BitSet with a manual shift.
It is the standard way subset-sum problems are pushed to larger bounds, and it changes no logic at all.
## Boundaries
1 2 4 8 answers 16: the powers of two make every subset total distinct, so the count
is 2^n. That is the maximum possible and the case where no collisions occur at all.
3 3 3 3 answers 5, namely 0 3 6 9 12, which is the opposite extreme: sixteen subsets
collapse to five totals.
The count is at most S + 1, which fits comfortably, but S itself sizes the table.