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.

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

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.

3. 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.