Algorithms
Hard
2902
3091
Count of Sub-Multisets With Bounded Sum
count-of-sub-multisets-with-bounded-sum
"""
You are given a 0-indexed array nums of non-negative integers, and two integers l and r.

Return the count of sub-multisets within nums where the sum of elements in each subset falls within the inclusive range of [l, r].

Since the answer may be large, return it modulo 109 + 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.

Note that:

 * Two sub-multisets are the same if sorting both sub-multisets results in identical multisets.
 * The sum of an empty multiset is 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}.

Constraints:

 * 1 <= nums.length <= 2 * 104
 * 0 <= nums[i] <= 2 * 104
 * Sum of nums does not exceed 2 * 104.
 * 0 <= l <= r <= 2 * 104
"""
class Solution:
    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
        
You are given a 0-indexed array nums of non-negative integers, and two integers l and r.

Return the count of sub-multisets within nums where the sum of elements in each subset falls within the inclusive range of [l, r].

Since the answer may be large, return it modulo 109 + 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.

Note that:

 * Two sub-multisets are the same if sorting both sub-multisets results in identical multisets.
 * The sum of an empty multiset is 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}.

Constraints:

 * 1 <= nums.length <= 2 * 104
 * 0 <= nums[i] <= 2 * 104
 * Sum of nums does not exceed 2 * 104.
 * 0 <= l <= r <= 2 * 104


Please complete the code below to solve above prblem:
```python
class Solution:
    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [1,2,2,3], "l": 6, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,1,4,2,7], "l": 1, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 7

test_input = { "nums": [1,2,1,3,5,2], "l": 3, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 9

test_input = { "nums": [0,0,1,2,3], "l": 2, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 9

test_input = { "nums": [0,0,0,0,0], "l": 0, "r": 0 }
assert my_solution.countSubMultisets(**test_input) == 6

test_input = { "nums": [0,0,0,1,2,5,2,3], "l": 0, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 20

test_input = { "nums": [1,1], "l": 2, "r": 2 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,1,1], "l": 2, "r": 2 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,1,2], "l": 2, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [1,2,1], "l": 2, "r": 2 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [1,2,2], "l": 3, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [2,1,1], "l": 1, "r": 2 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [2,1,2], "l": 2, "r": 2 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,2,1], "l": 4, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [2,2,2], "l": 3, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [1,1,1,1], "l": 3, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,1,1,2], "l": 1, "r": 1 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,1,1,3], "l": 4, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,1,2,1], "l": 3, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [1,1,2,2], "l": 2, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [1,1,2,3], "l": 4, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [1,1,3,1], "l": 2, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [1,1,3,2], "l": 6, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,1,3,3], "l": 8, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,2,1,1], "l": 3, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [1,2,1,2], "l": 4, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [1,2,1,3], "l": 4, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 6

test_input = { "nums": [1,2,2,1], "l": 4, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [1,2,2,2], "l": 1, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 7

test_input = { "nums": [1,2,2,3], "l": 3, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 9

test_input = { "nums": [1,2,3,1], "l": 1, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 7

test_input = { "nums": [1,2,3,2], "l": 4, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 7

test_input = { "nums": [1,2,3,3], "l": 6, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [1,3,1,1], "l": 6, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,3,1,2], "l": 7, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,3,1,3], "l": 5, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [1,3,2,1], "l": 2, "r": 2 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [1,3,2,2], "l": 7, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [1,3,2,3], "l": 1, "r": 9 }
assert my_solution.countSubMultisets(**test_input) == 11

test_input = { "nums": [1,3,3,1], "l": 7, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,3,3,2], "l": 1, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 8

test_input = { "nums": [1,3,3,3], "l": 9, "r": 10 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [2,1,1,1], "l": 2, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [2,1,1,2], "l": 1, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 6

test_input = { "nums": [2,1,1,3], "l": 7, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,1,2,1], "l": 3, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,1,2,2], "l": 6, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [2,1,2,3], "l": 7, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,1,3,1], "l": 4, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [2,1,3,2], "l": 3, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [2,1,3,3], "l": 1, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 6

test_input = { "nums": [2,2,1,1], "l": 6, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,2,1,2], "l": 2, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [2,2,1,3], "l": 6, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [2,2,2,1], "l": 4, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [2,2,2,2], "l": 3, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [2,2,2,3], "l": 5, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [2,2,3,1], "l": 7, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,2,3,2], "l": 5, "r": 9 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [2,2,3,3], "l": 4, "r": 10 }
assert my_solution.countSubMultisets(**test_input) == 6

test_input = { "nums": [2,3,1,1], "l": 4, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 5

test_input = { "nums": [2,3,1,2], "l": 3, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [2,3,1,3], "l": 2, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 9

test_input = { "nums": [2,3,2,1], "l": 3, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [2,3,2,2], "l": 3, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,3,2,3], "l": 5, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [2,3,3,1], "l": 9, "r": 9 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,3,3,2], "l": 8, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [2,3,3,3], "l": 3, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [3,1,1,1], "l": 4, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [3,1,1,2], "l": 7, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [3,1,1,3], "l": 1, "r": 1 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [3,1,2,1], "l": 4, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [3,1,2,2], "l": 3, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 9

test_input = { "nums": [3,1,2,3], "l": 5, "r": 9 }
assert my_solution.countSubMultisets(**test_input) == 6

test_input = { "nums": [3,1,3,1], "l": 1, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [3,1,3,2], "l": 3, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [3,1,3,3], "l": 9, "r": 10 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [3,2,1,1], "l": 1, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 9

test_input = { "nums": [3,2,1,2], "l": 1, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 9

test_input = { "nums": [3,2,1,3], "l": 5, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [3,2,2,1], "l": 4, "r": 4 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [3,2,2,2], "l": 6, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [3,2,2,3], "l": 2, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 6

test_input = { "nums": [3,2,3,1], "l": 2, "r": 3 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [3,2,3,2], "l": 8, "r": 10 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [3,2,3,3], "l": 1, "r": 11 }
assert my_solution.countSubMultisets(**test_input) == 7

test_input = { "nums": [3,3,1,1], "l": 8, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [3,3,1,2], "l": 2, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 5

test_input = { "nums": [3,3,1,3], "l": 1, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 5

test_input = { "nums": [3,3,2,1], "l": 4, "r": 6 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [3,3,2,2], "l": 7, "r": 10 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [3,3,2,3], "l": 4, "r": 10 }
assert my_solution.countSubMultisets(**test_input) == 4

test_input = { "nums": [3,3,3,1], "l": 6, "r": 9 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [3,3,3,2], "l": 11, "r": 11 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [3,3,3,3], "l": 8, "r": 9 }
assert my_solution.countSubMultisets(**test_input) == 1

test_input = { "nums": [1,1,1,1,1], "l": 3, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 3

test_input = { "nums": [1,1,1,1,2], "l": 2, "r": 5 }
assert my_solution.countSubMultisets(**test_input) == 7

test_input = { "nums": [1,1,1,1,3], "l": 6, "r": 7 }
assert my_solution.countSubMultisets(**test_input) == 2

test_input = { "nums": [1,1,1,1,4], "l": 8, "r": 8 }
assert my_solution.countSubMultisets(**test_input) == 1