Standard Bar Recursion · Subsequences Pattern O(n * sum) with memoization (the bare source recursion is exponential) · O(n * sum) memo table
A logistics bench holds crates of known weights and must know how many distinct kit combinations hit an exact payload target. Each crate is either in a kit or out, and the auditor counts kits — not arrangements — so two kits differing only in crate order are the same. Every time the running selection lands exactly on the target, the counter ticks; the answer is reported modulo 10^9 + 7.
Input: An array arr of n non-negative integers and an integer sum, the target.
Output: The number of subsets summing to the target, modulo 10^9 + 7.
1 <= n <= 10^30 <= arr[i] <= 10^30 <= sum <= 10^3Input: {"arr":[2,3,5,6,8,10],"sum":10}
Output: 3
The kits are {2, 3, 5}, {2, 8}, and {10}.
Input: {"arr":[1,1,4],"sum":5}
Output: 2
Both 1s are distinct crates, so {1a, 4} and {1b, 4} each count.