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 modulo 10^9 + 7.
  • A dp list is created with a size r + 1, initialized with 1 at index 0 and 0 for the rest. The dp[i] signifies the count of sub-multisets that sum up to i.
  • We remove the occurrences of 0 from the nums and keep its count in the variable zeros. The occurrences of 0 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 frequency freq in nums (excluding 0):
    • We copy the current dp list into another list called stride.
    • We update stride such that each stride[i] contains the sum of stride[i - num], stride[i - 2*num], ..., upto where i is still non-negative. This represents all possible sums with any number of num.

Step 3: Update DP Array with Frequency Constraints

  • For each index i in the stride list (in reverse from r to 1):
    • If i is greater than or equal to num * (freq + 1), subtract stride[i - num * (freq + 1)] from stride[i] to account for exceeding the frequency of num. Then set dp[i] to this updated value.
    • If it's less than that, just set dp[i] to stride[i].

Step 4: Handling Zeroes and Final Count

  • To handle the number of 0s that could be part of any sub-multiset, multiply the sum of dp[l : r + 1] by (zeros + 1), because for any given sum, you can either include or exclude a 0.

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 modulo kMod.

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 Evaluator

Example 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 of r + 1 = 3 + 1 = 4, so dp = [1, 0, 0, 0].
  • There are no 0s in nums, so zeros = 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 frequency freq = 2. We copy dp = [1, 0, 0, 0] to stride.
  • We update stride by considering num = 1:
    • i = 1: stride[1] becomes stride[0], so stride is now [1, 1, 0, 0].
    • i = 2: stride[2] becomes stride[1] + stride[0], so stride is now [1, 1, 2, 0].
    • i = 3: stride[3] becomes stride[2] + stride[1], so stride is now [1, 1, 2, 3].

Step 3: Update DP Array with Frequency Constraints

  • Since we have only used num = 1 with frequency 2 so far, no constraint is reached; thus we set dp = stride, so dp is now [1, 1, 2, 3].

Step 4: Processing the Next Number

  • Now we consider num = 2, frequency freq = 1.
  • We copy dp = [1, 1, 2, 3] to stride and then update it:
    • i = 2: stride[2] becomes stride[0], so stride is now [1, 1, 1, 3].
    • i = 3: stride[3] becomes stride[1], so stride is now [1, 1, 1, 1].
  • Update dp with consideration for num = 2 and freq = 1. No constraints are exceeded, and thus dp becomes [1, 1, 1, 1].

Step 5: Final Count and Handling Zeroes

  • In our range [l, r] = [2, 3], we have dp[2] = 1 and dp[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 than kMod.

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:

  1. Iterating over each unique number in nums except for zero: The iteration over count.items() runs for each unique number. Let U be the number of unique numbers in nums.

  2. Within the outer loop for each number num, two nested loops are used:

    • The first nested loop for computing stride: This loop runs from num to r, leading to approximately r/num iterations for each number num.
    • The second nested loop for updating dp: This loop runs in reverse from r to 1, resulting in r iterations.

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.

  1. The final computation of the result involves summing a slice of the dp array, which takes O(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:

  1. The dp and stride arrays: Both arrays have a size of r + 1, so their space requirement is O(r) each.

  2. The Counter object for counting frequencies of nums: The space requirement for this counter is proportional to the number of unique elements U, leading to a space complexity of O(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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How does quick sort divide the problem into subproblems?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More