2902. Count of Sub-Multisets With Bounded Sum
Problem Description
In this problem, we're given an array nums
containing non-negative integers and two integers l
and r
. Our task is to find out how many sub-multisets of this array have their sums in the inclusive range [l, r]
. A sub-multiset is an unordered collection of elements from the array, where each element in the collection can occur any number of times from zero up to its frequency in the original array.
For example, given nums = [1, 2, 2, 3]
, l = 6
, and r = 6
, there is only one sub-multiset whose sum is equal to 6, which is {1, 2, 3}
.
The challenge also requires that we calculate the answer modulo 10^9 + 7
, due to the possibility of large results.
Intuition
The intuition behind the provided solution is to use a dynamic programming approach to count the number of sub-multisets that sum up to every possible value from 0
to r
. Because our final answer needs to include all sub-multisets that have a sum between l
and r
, we will eventually sum up the counts for all sums in that range.
To account for the use of each number in nums
, a helper array dp
is maintained, which will hold the number of ways to achieve a specific sum i
. The problem states that we can use each unique number as many times as it appears in the initial array. Therefore, for each number num
and its frequency freq
, we need to update our dp
array to reflect all possible sums using 0
to freq
instances of num
.
Essentially, for each unique number, we are calculating a "stride" which consists of all the ways to form sums using that number. Then, we go through this stride in reverse, and utilize it to update our dp
values while making sure not to exceed the usage limits based on the frequency of each number.
After we've considered all numbers, we need to account for any zero values in our input array since they don't contribute to the sum but still represent valid sub-multiset elements. This contributes to the final count by multiplying the existing sum counts by one more than the number of zeros ((zeros + 1)
), as each sum can be formed with or without the inclusion of zero.
Finally, we sum up all the possible counts of sub-multisets whose sums lie within the given range, [l, r]
, and return that sum modulo 10^9 + 7
.
Learn more about Dynamic Programming and Sliding Window patterns.
Solution Approach
The solution uses dynamic programming along with a stride pattern to consider different combinations that create sub-multisets totaling each possible sum up to r
. Here's a step-by-step explanation of the implementation:
Step 1: Initial Setup
- Initialize a modulo constant
kMod = 1_000_000_007
to ensure all calculations are made modulo10^9 + 7
. - A
dp
list is created with a sizer + 1
, initialized with1
at index0
and0
for the rest. Thedp[i]
signifies the count of sub-multisets that sum up toi
. - We remove the occurrences of
0
from thenums
and keep its count in the variablezeros
. The occurrences of0
are handled separately at the end since they don't add to the sum of the sub-multiset.
Step 2: Populate DP Array for Each Number
- For each unique number
num
and its frequencyfreq
innums
(excluding0
):- We copy the current
dp
list into another list calledstride
. - We update
stride
such that eachstride[i]
contains the sum ofstride[i - num]
,stride[i - 2*num]
, ..., upto wherei
is still non-negative. This represents all possible sums with any number ofnum
.
- We copy the current
Step 3: Update DP Array with Frequency Constraints
- For each index
i
in thestride
list (in reverse fromr
to1
):- If
i
is greater than or equal tonum * (freq + 1)
, subtractstride[i - num * (freq + 1)]
fromstride[i]
to account for exceeding the frequency ofnum
. Then setdp[i]
to this updated value. - If it's less than that, just set
dp[i]
tostride[i]
.
- If
Step 4: Handling Zeroes and Final Count
- To handle the number of
0s
that could be part of any sub-multiset, multiply the sum ofdp[l : r + 1]
by(zeros + 1)
, because for any given sum, you can either include or exclude a0
.
Step 5: Return the Result
- The final step is to return the counting sum of
dp[l : r + 1]
multiplied by(zeros + 1)
and taken modulokMod
.
Through these steps, the algorithm calculates the sub-multiset counts effectively, leveraging the properties of combinatorial sums and dynamic programming, thereby providing a solution that works within the constraint limits for large values of nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example using the array nums = [1, 2, 1]
, and we want to find the count of sub-multisets with sums in the range [l, r] = [2, 3]
.
Step 1: Initial Setup
- We set
kMod = 1_000_000_007
for modulo operations. - Initialize
dp
with a size ofr + 1 = 3 + 1 = 4
, sodp = [1, 0, 0, 0]
. - There are no
0
s innums
, sozeros = 0
.
Step 2: Populate DP Array for Each Number
- Since
nums
has duplicates, we're going to process each unique number and its frequency. - For
1
, its frequencyfreq = 2
. We copydp = [1, 0, 0, 0]
tostride
. - We update
stride
by consideringnum = 1
:i = 1
:stride[1]
becomesstride[0]
, sostride
is now[1, 1, 0, 0]
.i = 2
:stride[2]
becomesstride[1] + stride[0]
, sostride
is now[1, 1, 2, 0]
.i = 3
:stride[3]
becomesstride[2] + stride[1]
, sostride
is now[1, 1, 2, 3]
.
Step 3: Update DP Array with Frequency Constraints
- Since we have only used
num = 1
with frequency2
so far, no constraint is reached; thus we setdp = stride
, sodp
is now[1, 1, 2, 3]
.
Step 4: Processing the Next Number
- Now we consider
num = 2
, frequencyfreq = 1
. - We copy
dp = [1, 1, 2, 3]
tostride
and then update it:i = 2
:stride[2]
becomesstride[0]
, sostride
is now[1, 1, 1, 3]
.i = 3
:stride[3]
becomesstride[1]
, sostride
is now[1, 1, 1, 1]
.
- Update
dp
with consideration fornum = 2
andfreq = 1
. No constraints are exceeded, and thusdp
becomes[1, 1, 1, 1]
.
Step 5: Final Count and Handling Zeroes
- In our range
[l, r] = [2, 3]
, we havedp[2] = 1
anddp[3] = 1
. - Since there are no
zeros
, we don't adjust for them. - Our final count is the sum of these values:
1 + 1 = 2
.
Step 6: Return the Result
- We return the count
2
. No modulo operation is needed since the count is already less thankMod
.
By following these steps, we find that there are 2 sub-multisets with sums in the range [2, 3]
from our nums
array: {1, 1}
and {2}
. These steps demonstrate how the dynamic programming approach with frequency constraints is applied to solve this problem.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def count_sub_multisets(self, nums: List[int], left: int, right: int) -> int:
5 MOD_VALUE = 1_000_000_007
6
7 # dp[i] stores the number of submultisets of nums with sum i.
8 dp = [1] + [0] * right
9 num_counts = Counter(nums)
10
11 # Extract and remove the count of zeros present in nums, as they do not contribute to the sum.
12 zero_count = num_counts.pop(0, 0)
13
14 for num, frequency in num_counts.items():
15 # stride[i] is the cumulative sum needed to calculate the new dp[i] considering the current number.
16 stride = dp.copy()
17 for i in range(num, right + 1):
18 stride[i] += stride[i - num]
19
20 # Update dp[i] based on the count of the current number available for use.
21 for i in range(right, 0, -1):
22 if i >= num * (frequency + 1):
23 # Remove the contribution beyond the frequency limit.
24 dp[i] = (stride[i] - stride[i - num * (frequency + 1)]) % MOD_VALUE
25 else:
26 # Within the frequency limit, use the previously computed sum directly.
27 dp[i] = stride[i]
28
29 # Calculate the total number of valid submultisets with sum within the given range [left, right].
30 # Account for multiple subsets with zeros by multiplying with (zero_count + 1).
31 total_sub_multisets = sum(dp[left:right + 1]) * (zero_count + 1)
32
33 # Return the result modulo MOD_VALUE to avoid large numbers.
34 return total_sub_multisets % MOD_VALUE
35
1class Solution {
2 // The modulo constant as specified in the problem
3 private static final int MOD = 1_000_000_007;
4
5 // Count the number of sub-multisets with sum in the range [l, r]
6 public int countSubMultisets(List<Integer> nums, int l, int r) {
7 // Count the frequency of each number in nums
8 Map<Integer, Integer> frequencyMap = new HashMap<>();
9 int totalSum = 0; // Variable to store the total sum of numbers
10
11 // Accumulate counts for each number and compute the total sum
12 for (int num : nums) {
13 totalSum += num;
14 // Only consider numbers that are within the specified range [1, r]
15 if (num <= r) {
16 frequencyMap.merge(num, 1, Integer::sum);
17 }
18 }
19
20 // If total sum is less than l, no subsets can have sum in [l, r]
21 if (totalSum < l) {
22 return 0;
23 }
24 // Restrict upper bound to the minimum of totalSum and r
25 r = Math.min(r, totalSum);
26
27 int[] dp = new int[r + 1]; // Dynamic programming array
28 // Base case: there's always one empty subset that sums to 0
29 dp[0] = frequencyMap.getOrDefault(0, 0) + 1;
30 frequencyMap.remove(0); // Remove zero count from map, if present
31
32 int currentMaxSum = 0; // Variable to keep track of the maximum sum we calculate
33 // Iterate through each entry in the frequency map
34 for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
35 int num = entry.getKey();
36 int frequency = entry.getValue();
37 currentMaxSum = Math.min(currentMaxSum + frequency * num, r);
38
39 // Prefix part - calculate new dp values based on the number and its frequency.
40 for (int i = num; i <= currentMaxSum; i++) {
41 dp[i] = (dp[i] + dp[i - num]) % MOD;
42 }
43
44 // Correction part - removes counts incorrectly included from previous iterations.
45 int temp = (frequency + 1) * num;
46 for (int i = currentMaxSum; i >= temp; i--) {
47 dp[i] = (dp[i] - dp[i - temp] + MOD) % MOD;
48 }
49 }
50
51 // Calculate the answer by summing dp values within range [l, r]
52 int answer = 0;
53 for (int i = l; i <= r; i++) {
54 answer = (answer + dp[i]) % MOD;
55 }
56
57 return answer; // Return the computed answer
58 }
59}
60
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7 // The modulo constant as specified in the problem
8 static const int MOD = 1'000'000'007;
9
10public:
11 // Count the number of sub-multisets with sum in the range [l, r]
12 int countSubMultisets(vector<int>& nums, int l, int r) {
13 // Count the frequency of each number in nums
14 unordered_map<int, int> frequency_map;
15 int total_sum = 0; // Variable to store the total sum of numbers
16
17 // Accumulate counts for each number and compute the total sum
18 for (int num : nums) {
19 total_sum += num;
20 // Only consider numbers that are within the specified range [1, r]
21 if (num <= r) {
22 frequency_map[num]++;
23 }
24 }
25
26 // If total sum is less than l, no subsets can have sum in [l, r]
27 if (total_sum < l) {
28 return 0;
29 }
30 // Restrict upper bound to the minimum of total_sum and r
31 r = min(r, total_sum);
32
33 vector<int> dp(r + 1, 0); // Dynamic programming array
34 // Base case: there's always one empty subset that sums to 0
35 dp[0] = frequency_map.count(0) ? frequency_map[0] + 1 : 1;
36 frequency_map.erase(0); // Remove zero count from map, if present
37
38 int current_max_sum = 0; // Variable to keep track of the maximum sum we calculate
39 // Iterate through each entry in the frequency map
40 for (const auto& entry : frequency_map) {
41 int num = entry.first;
42 int frequency = entry.second;
43 current_max_sum = min(current_max_sum + frequency * num, r);
44
45 // Prefix part - calculate new dp values based on the number and its frequency.
46 for (int i = current_max_sum; i >= num; --i) {
47 dp[i] = (dp[i] + dp[i - num]) % MOD;
48 }
49
50 // Correction part - removes counts incorrectly included from previous iterations.
51 int temp = (frequency + 1) * num;
52 for (int i = current_max_sum; i >= temp; --i) {
53 dp[i] = (dp[i] - dp[i - temp] + MOD) % MOD;
54 }
55 }
56
57 // Calculate the answer by summing dp values within range [l, r]
58 int answer = 0;
59 for (int i = l; i <= r; ++i) {
60 answer = (answer + dp[i]) % MOD;
61 }
62
63 return answer; // Return the computed answer
64 }
65};
66
1// The modulo constant as specified in the problem
2const MOD = 1_000_000_007;
3
4/**
5 * Count the frequency of each number in nums
6 * @param nums The list of numbers.
7 * @returns A map with frequency of each number.
8 */
9function countFrequency(nums: number[]): Map<number, number> {
10 const frequencyMap = new Map<number, number>();
11 for (const num of nums) {
12 frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
13 }
14 return frequencyMap;
15}
16
17/**
18 * Count the number of sub-multisets with sum in the range [l, r]
19 * @param nums The list of numbers.
20 * @param l The lower bound of the sum range.
21 * @param r The upper bound of the sum range.
22 * @returns The count of sub-multisets.
23 */
24function countSubMultisets(nums: number[], l: number, r: number): number {
25 const frequencyMap = countFrequency(nums.filter(num => num <= r));
26
27 let totalSum = nums.reduce((acc, num) => acc + num, 0);
28 if (totalSum < l) {
29 return 0;
30 }
31 r = Math.min(r, totalSum);
32
33 const dp: number[] = new Array(r + 1).fill(0);
34 dp[0] = 1 + (frequencyMap.get(0) || 0); // Including empty set
35 frequencyMap.delete(0);
36
37 let currentMaxSum = 0;
38 for (const [num, frequency] of frequencyMap.entries()) {
39 currentMaxSum = Math.min(currentMaxSum + frequency * num, r);
40
41 // Prefix part - calculate new dp values based on the number and its frequency
42 for (let i = num; i <= currentMaxSum; i++) {
43 dp[i] = (dp[i] + dp[i - num]) % MOD;
44 }
45
46 // Correction part - removes counts incorrectly included from previous iterations
47 const temp = (frequency + 1) * num;
48 for (let i = currentMaxSum; i >= temp; i--) {
49 dp[i] = (dp[i] - dp[i - temp] + MOD) % MOD;
50 }
51 }
52
53 // Calculate the answer by summing dp values within range [l, r]
54 let answer = 0;
55 for (let i = l; i <= r; i++) {
56 answer = (answer + dp[i]) % MOD;
57 }
58
59 return answer;
60}
61
Time and Space Complexity
The given Python code is designed to calculate the number of submultisets of the input list nums
whose sum is between l
and r
, inclusive. This computation involves dynamic programming and leveraging properties of the submultiset problem. The analysis of time and space complexities is as follows:
Time Complexity
The time complexity can be analyzed based on the loops and operations in the code:
-
Iterating over each unique number in
nums
except for zero: The iteration overcount.items()
runs for each unique number. LetU
be the number of unique numbers innums
. -
Within the outer loop for each number
num
, two nested loops are used:- The first nested loop for computing
stride
: This loop runs fromnum
tor
, leading to approximatelyr/num
iterations for each numbernum
. - The second nested loop for updating
dp
: This loop runs in reverse fromr
to1
, resulting inr
iterations.
- The first nested loop for computing
The heaviest computational load comes from these two loops, which for each unique num
, perform operations proportional to r
.
If N
represents the size of the input list nums
, the overall worst-case time complexity is approximated by O(U * r)
, where r
is the upper bound on the submultiset sum.
- The final computation of the result involves summing a slice of the
dp
array, which takesO(r - l + 1)
time.
Considering all the above, the cumulative time complexity is O(U * r + r - l + 1)
, which simplifies to O(U * r)
assuming U
and r-l
are much smaller than r
.
Space Complexity
The space complexity is determined by the storage requirements:
-
The
dp
andstride
arrays: Both arrays have a size ofr + 1
, so their space requirement isO(r)
each. -
The
Counter
object for counting frequencies ofnums
: The space requirement for this counter is proportional to the number of unique elementsU
, leading to a space complexity ofO(U)
.
Since dp
and stride
are the largest data structures and no additional space that scales with the input size is used, the overall space complexity of the algorithm is O(r + U)
.
However, since U
cannot exceed r
, as that is the maximum sum of any submultiset, the space complexity can be simplified to O(r)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!