Count Subsets With a Sum
Count the subsets of the given numbers whose total is exactly S. Subsets are
identified by WHICH POSITIONS they use, so equal values at different positions give
different subsets. Values may be zero.
Print the count modulo 1000000007.
1 2 3 4, S = 5 -> 2 {1,4} and {2,3}
1 1 1 1, S = 2 -> 6 any two of the four positions
The second line is the convention made explicit. All four values are equal, and the
answer is 4 choose 2 = 6, not 1. Counting by position rather than by value is the
only reading that makes the count well defined here.
## The recurrence
Problem #422 asks whether a target is reachable. This asks how many ways, and the change is the same one as everywhere: replace the boolean OR with an addition.
dp[0] = 1
for each value v:
for t from S down to v:
dp[t] += dp[t - v]
## Why the inner loop runs backward
Each position may be used at most ONCE, so when dp[t] reads dp[t - v] it must read
the value from BEFORE this item was processed.
Going downward guarantees that, because t - v is below t and has not been touched
yet in this pass. Going upward would let dp[t - v] already include v, which means
using the same position twice, and that is problem 482's unbounded counting.
One loop direction separates "at most once" from "as often as you like". It is worth being able to say which is which without checking.
## Zeros, which is the case that catches people
A value of 0 can be in or out of a subset without changing the total, so every zero DOUBLES the count.
0 0 1 with S = 1 answers 4: the 1 must be in, and each zero is independently in or
out. A solution that skips zeros, or that starts the inner loop at max(v, 1), answers
1.
The general loop handles it with no special case, and it is worth seeing why. With
v = 0 the inner loop runs from S down to 0 and performs dp[t] += dp[t - 0], which
is dp[t] += dp[t], doubling every entry. That is exactly right.
## Boundaries
S = 0 is not in the tests but is worth thinking about: the empty subset always
qualifies, so the answer is at least 1, and each zero doubles it.
3 with S = 5 answers 0. Unreachable means a count of zero, not -1.
The count reaches 2^n, so the modulus is not decoration.