Standard Bar Dynamic Programming · DP on Subsequences O(n*S) · O(S)
A datacenter splits its battery cells between two backup racks. Site policy requires the heavier rack to outweigh the lighter one by exactly d kilowatt-hours — no other gap qualifies. The facilities engineer counts how many ways the cells can be assigned while honoring the precise power differential.
Input: An integer n, a difference d, and an array arr of n non-negative integers.
Output: Return the number of partitions into subsets S1, S2 with S1 >= S2 and sum(S1) - sum(S2) = d, modulo 10^9 + 7.
1 <= n <= 10^30 <= d <= 10^40 <= arr[i] <= 10^3answer modulo 10^9 + 7Input: {"n":4,"d":3,"arr":[5,2,6,4]}
Output: 1
Only {6, 4} versus {5, 2} gives 10 - 7 = 3.
Input: {"n":3,"d":1,"arr":[1,1,1]}
Output: 3
Pick any two cells for the heavy rack and the last for the light one — three ways, gap 1 each time.