2902. Count of Sub-Multisets With Bounded Sum LeetCode Solution
In this guide, you will get 2902. Count of Sub-Multisets With Bounded Sum LeetCode Solution with the best time and space complexity. The solution to Count of Sub-Multisets With Bounded Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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}.
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
Complexity Analysis
Time Complexity: O(r\cdot\sqrt{\Sigma(\texttt{nums[i]})})
Space Complexity: O(r)
2902. Count of Sub-Multisets With Bounded Sum LeetCode Solution in C++
class Solution {
public:
int countSubMultisets(vector<int>& nums, int l, int r) {
constexpr int kMod = 1'000'000'007;
// dp[i] := the number of submultisets of `nums` with sum i
vector<long> dp(r + 1);
dp[0] = 1;
unordered_map<int, int> count;
for (const int num : nums)
++count[num];
const int zeros = count[0];
count.erase(0);
for (const auto& [num, freq] : count) {
// stride[i] := dp[i] + dp[i - num] + dp[i - 2 * num] + ...
vector<long> stride = dp;
for (int i = num; i <= r; ++i)
stride[i] += stride[i - num];
for (int i = r; i > 0; --i)
if (i >= num * (freq + 1))
// dp[i] + dp[i - num] + dp[i - freq * num]
dp[i] = (stride[i] - stride[i - num * (freq + 1)]) % kMod;
else
dp[i] = stride[i] % kMod;
}
long ans = 0;
for (int i = l; i <= r; ++i)
ans = (ans + dp[i]) % kMod;
return ((zeros + 1) * ans) % kMod;
}
}; /* code provided by PROGIEZ */
2902. Count of Sub-Multisets With Bounded Sum LeetCode Solution in Java
class Solution {
public int countSubMultisets(List<Integer> nums, int l, int r) {
final int kMod = 1_000_000_007;
// dp[i] := the number of submultisets of `nums` with sum i
long[] dp = new long[r + 1];
dp[0] = 1;
Map<Integer, Integer> count = new HashMap<>();
for (final int num : nums)
count.merge(num, 1, Integer::sum);
final int zeros = count.containsKey(0) ? count.remove(0) : 0;
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
final int num = entry.getKey();
final int freq = entry.getValue();
// stride[i] := dp[i] + dp[i - num] + dp[i - 2 * num] + ...
long[] stride = dp.clone();
for (int i = num; i <= r; ++i)
stride[i] += stride[i - num];
for (int i = r; i > 0; --i)
if (i >= num * (freq + 1))
// dp[i] + dp[i - num] + dp[i - freq * num]
dp[i] = (stride[i] - stride[i - num * (freq + 1)]) % kMod;
else
dp[i] = stride[i] % kMod;
}
long ans = 0;
for (int i = l; i <= r; ++i)
ans = (ans + dp[i]) % kMod;
return (int) (((zeros + 1) * ans) % kMod);
}
} // code provided by PROGIEZ
2902. Count of Sub-Multisets With Bounded Sum LeetCode Solution in Python
class Solution:
def countSubMultisets(self, nums: list[int], l: int, r: int) -> int:
kMod = 1_000_000_007
# dp[i] := the number of submultisets of `nums` with sum i
dp = [1] + [0] * r
count = collections.Counter(nums)
zeros = count.pop(0, 0)
for num, freq in count.items():
# stride[i] := dp[i] + dp[i - num] + dp[i - 2 * num] + ...
stride = dp.copy()
for i in range(num, r + 1):
stride[i] += stride[i - num]
for i in range(r, 0, -1):
if i >= num * (freq + 1):
# dp[i] + dp[i - num] + dp[i - freq * num]
dp[i] = stride[i] - stride[i - num * (freq + 1)]
else:
dp[i] = stride[i]
return (zeros + 1) * sum(dp[l:r + 1]) % kMod # code by PROGIEZ
