490. 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.

Constraints - `1 ≤ n ≤ 200` - `0 ≤ value ≤ 500`