496. Subsets With a Given Difference
Split EVERY number into two groups, the first minus the second having total exactly
D. Count the ways to do it, identifying a split by which POSITIONS go into the first
group.
Print the count modulo 1000000007.
1 1 2 3, D = 1 -> 3
1 2 7, D = 4 -> 1
## The reduction
Let total be the sum of everything and T the total of the first group. The second
group gets total - T, so
T - (total - T) = D hence T = (total + D) / 2
Every number must be placed, so once the first group is chosen the second is determined.
The question becomes: how many subsets total exactly T.
That is problem 483, and the entire content of this problem is arriving at T. A
difference constraint on a partition is a sum constraint on one side, and seeing that is
worth more than the three lines that follow.
## The two feasibility conditions
T has to be a non-negative integer:
total + D must be EVEN otherwise the answer is 0
T = (total + D) / 2 must satisfy 0 <= T <= total
The parity test is the one people forget, and it is not an edge case. 1 with D = 0
answers 0: the total is 1, total + D = 1 is odd, and no split of a single odd number
can have equal halves. Skip the test and T becomes 0 by integer division, the count
comes back 1 for the empty first group, and the reported split has difference -1
rather than 0.
The upper test catches D larger than the total, where even putting everything in the
first group falls short.
## Zeros
A zero can sit in either group without changing the difference, so each zero DOUBLES the
count. 0 0 1 with D = 1 answers 4.
That falls out of problem 483's handling, where the inner loop bound must be t >= v
rather than t > v so that v = 0 performs dp[t] += dp[t].
## Boundaries
1 1 1 1 with D = 0 answers 6, which is 4 choose 2: the first group must total 2,
and any two of the four positions do it.
2 2 with D = 0 answers 2, one for each position going first. Not 1: the two groups
are distinguishable, since the statement names the first and second explicitly.
5 5 5 with D = 5 answers 3. The total is 15, T = 10, which is any two of the
three.
## Cost
Time O(n T). Space O(T).
Constraints - `1 ≤ n ≤ 200` - `0 ≤ D ≤ 20000` - `0 ≤ value ≤ 1000`
Input
The first line contains two integers n and D.
The second line contains n space-separated non-negative integers.
Output
Print the number of ways to split every number into a first and second group whose totals differ by exactly D, modulo 1000000007.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.