Count Partitions with Given Difference

Assign every array position exactly once to named groups S1 or S2 so that sum(S1) - sum(S2) equals the nonnegative difference diff. Count assignments modulo…

Assign every array position exactly once to named groups S1 or S2 so that sum(S1) - sum(S2) equals the nonnegative difference diff. Count assignments modulo 1,000,000,007. Empty groups are allowed. Equal values remain distinct positions. At difference zero, complementary named assignments are distinct; do not divide by two.

- 1 <= n <= 200; 0 <= arr[i] <= 50; 0 <= diff <= 10000. - Assigning a zero position to S1 or S2 gives two distinct assignments. - Visualization accepts at most 6 items and transformed capacity at most 10; larger valid inputs are coding-only. Infeasible range/parity cases terminate before table allocation.

Example 1: input values = [0,0,1], target = 1; output 4. The two zero positions each have two distinct choices, multiplying the one feasible assignment by four.

Example 2: input values = [1,1], target = 0; output 2. Either indexed 1 can belong to S1 while the other belongs to S2. The groups are named, so the complementary assignment is counted separately.

Example 3: input values = [1,2], target = 0; output 0. The total is 3. Equal group sums would each have to be 1.5, which is impossible for integer-valued positions.

Category: Arrays. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.