Watch 3 video solutions for Count of Sub-Multisets With Bounded Sum, a hard level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by codingMohan has 1,933 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |