Standard Bar Dynamic Programming · DP on Subsequences O(n*sum) · O(sum)
An aircraft depot tags every spare part with a weight, and the compliance team wants to know how many distinct bundles weigh exactly the certified payload k. Parts are physically distinct even when weights repeat, and a bundle is only a bundle if the total matches the certificate to the gram. The audit program counts every qualifying selection.
Input: An integer n, an array arr of n non-negative integers, and a target sum.
Output: Return the number of distinct subsets of arr whose elements sum to the target, modulo 10^9 + 7.
1 <= n <= 10^30 <= arr[i] <= 10^30 <= sum <= 10^3answer modulo 10^9 + 7Input: {"n":6,"arr":[2,3,5,6,8,10],"sum":10}
Output: 3
{2, 3, 5}, {2, 8}, and {10} each total 10.
Input: {"n":2,"arr":[1,1],"sum":1}
Output: 2
Either copy of the part alone is a valid distinct bundle.