2902. Count of Sub-Multisets With Bounded Sum
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []


class Solution:
    def countSubMultisets(self, A: List[int], l: int, r: int) -> int:
        MODULO = 10 ** 9 + 7
        max_sum = 50000
        ways = [1] + [0] * max_sum
        element_counts = Counter(A)

        for value, frequency in element_counts.items():
            for target in range(r, max(r - value, 0), -1):
                current_sum = sum(ways[target - value * multiplier] for multiplier in range(frequency))
                for step in range(target, 0, -value):
                    current_sum -= ways[step] - ways[step - value * frequency]
                    ways[step] = (ways[step] + current_sum) % MODULO

        total_count = (element_counts[0] + 1) * sum(ways[l:r + 1]) % MODULO
        return total_count

```
['Python3']