#2902
Count of Sub-Multisets With Bounded Sum
international master · 2165 · lc hard +32 · verified · 22.3% accepted · 163 likes · top 2%
Description
A 0-indexed array nums of non-negative integers and two integers l and r are given.
Count all sub-multisets of nums whose element sum falls within [l, r].
Return the count modulo 109 + 7.
A sub-multiset uses each value x between 0 and occ[x] times, where occ[x] is its frequency in nums.
Notes:
- Two sub-multisets are identical if their sorted forms are the same.
- An empty multiset has sum 0.
Example 1:
Input: nums = [1,2,2,3], l = 6, r = 6
Output: 1
Explanation: The only subset of nums that has a sum of 6 is {1, 2, 3}.
Example 2:
Input: nums = [2,1,4,2,7], l = 1, r = 5
Output: 7
Explanation: The subsets of nums that have a sum within the range [1, 5] are {1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4}, and {1, 2, 2}.
Example 3:
Input: nums = [1,2,1,3,5,2], l = 3, r = 5
Output: 9
Explanation: The subsets of nums that have a sum within the range [3, 5] are {3}, {5}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {1, 1, 2}, {1, 1, 3}, and {1, 2, 2}.
Code
1
2
3