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:
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 * 1040 <= nums[i] <= 2 * 104nums does not exceed 2 * 104.0 <= l <= r <= 2 * 104Problem Overview: You receive an integer array that represents a multiset. The task is to count how many sub-multisets have a total sum within a range [l, r]. Since duplicates are allowed and each value can be used multiple times (up to its frequency), the problem becomes a bounded subset-sum counting problem.
Approach 1: Dynamic Programming with Sliding Window Optimization (O(U * r) time, O(r) space)
Start by compressing the array into a frequency map using a hash table. Each unique value v appears cnt times. Define a DP array where dp[s] represents the number of ways to build sum s. This resembles a bounded knapsack problem. For each value, update the DP states using a prefix-sum or sliding window trick so you avoid iterating cnt times explicitly. The window maintains contributions from dp[s - k*v] for k within the allowed count. This optimization reduces the transition from O(cnt * r) to O(r). The final answer is the sum of dp[s] for s between l and r. The approach relies heavily on dynamic programming with a window-style prefix sum similar to techniques used in sliding window problems.
Approach 2: Combinatorial Counting with Frequency Compression (O(U * r) time, O(r) space)
Instead of thinking about individual elements, treat the array as groups of identical values. For each value v with frequency cnt, you can pick it 0..cnt times. The total contribution to the sum is therefore k * v. Build a DP array that counts combinations while iterating over unique values. For every sum s, accumulate contributions from valid previous states while respecting the upper bound on how many times v can appear. Prefix sums or difference arrays help efficiently subtract states that exceed the allowed count. This turns the naive combinatorial enumeration into a linear scan over possible sums. The technique is conceptually similar to generating function multiplication but implemented iteratively with arrays.
Recommended for interviews: The optimized dynamic programming approach is what interviewers typically expect. Recognizing that the problem is a bounded knapsack variant shows good pattern recognition. Implementing the prefix-sum sliding window optimization demonstrates strong DP skills and avoids the quadratic blow-up that a naive DP would cause.
This approach leverages dynamic programming to track possible sums using a bitset or a boolean array up to the maximum possible sum. Initially, the set only contains the empty sub-multiset sum of zero. We iterate over each number in the given array, updating the set of attainable sums by considering each number's contribution to prior sums. Once we compute all possible sums, we count those within the range [l, r]. To handle large outputs, a modulus operation is employed, complying with the problem constraints.
In this C solution, we use an array dp to keep track of the attainable sums. We initialize dp[0] as 1 to signify the empty set. As we iterate through each number, we update the sum possibilities in the array by iterating in reverse order to prevent over-counting. Once all possible sums are identified, we sum the relevant counts within [l, r].
Time Complexity: O(n * m), where n is the number of elements and m is the maximum sum, Space Complexity: O(m), where m is the maximum boundary for sums.
This approach uses combinatorial counting with inclusion-exclusion principle. For each number in the array, we compute how many times each sum can be formed and employ counting techniques to find the number of subsets in the range [l, r]. This can involve computing all subset sums for all combinations of numbers, but uses inclusion-exclusion principles and combinatorial calculations to efficiently tally possible subset counts.
This C solution outlines the structure for a combinatorial counting method based on binomial coefficients. However, implementing full combinatorial logic is intricate, especially for large ranges, and typically more efficiently codified in higher-level languages supporting big integer computations.
The time complexity of computing binomial coefficients typically exceeds O(2^n) in a naive implementation, with space complexity directly proportional to the subset totals reviewed.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * m), where n is the number of elements and m is the maximum sum, Space Complexity: O(m), where m is the maximum boundary for sums. |
| Combinatorial Counting Approach | The time complexity of computing binomial coefficients typically exceeds O(2^n) in a naive implementation, with space complexity directly proportional to the subset totals reviewed. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Sliding Window | O(U * r) | O(r) | General case; optimal solution for bounded subset-sum counting |
| Combinatorial Counting with Frequency Compression | O(U * r) | O(r) | Useful when reasoning about combinations of identical values |
2902. Count of Sub-Multisets With Bounded Sum | Leetcode Biweekly 115 • codingMohan • 1,933 views views
Watch 2 more video solutions →Practice Count of Sub-Multisets With Bounded Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor