2902. Count of Sub-Multisets With Bounded Sum Hard

1/**
2 * [2902] Count of Sub-Multisets With Bounded Sum
3 *
4 * You are given a 0-indexed array nums of non-negative integers, and two integers l and r.
5 * Return the count of sub-multisets within nums where the sum of elements in each subset falls within the inclusive range of [l, r].
6 * Since the answer may be large, return it modulo 10^9 + 7.
7 * A sub-multiset is an unordered collection of elements of the array in which a given value x can occur 0, 1, ..., occ[x] times, where occ[x] is the number of occurrences of x in the array.
8 * Note that:
9 * 
10 * 	Two sub-multisets are the same if sorting both sub-multisets results in identical multisets.
11 * 	The sum of an empty multiset is 0.
12 * 
13 *  
14 * Example 1:
15 * 
16 * Input: nums = [1,2,2,3], l = 6, r = 6
17 * Output: 1
18 * Explanation: The only subset of nums that has a sum of 6 is {1, 2, 3}.
19 * 
20 * Example 2:
21 * 
22 * Input: nums = [2,1,4,2,7], l = 1, r = 5
23 * Output: 7
24 * 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}.
25 * 
26 * Example 3:
27 * 
28 * Input: nums = [1,2,1,3,5,2], l = 3, r = 5
29 * Output: 9
30 * 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}.
31 *  
32 * Constraints:
33 * 
34 * 	1 <= nums.length <= 2 * 10^4
35 * 	0 <= nums[i] <= 2 * 10^4
36 * 	Sum of nums does not exceed 2 * 10^4.
37 * 	0 <= l <= r <= 2 * 10^4
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/count-of-sub-multisets-with-bounded-sum/
43// discuss: https://leetcode.com/problems/count-of-sub-multisets-with-bounded-sum/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn count_sub_multisets(nums: Vec<i32>, l: i32, r: i32) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_2902() {
61    }
62}
63