Count of Sub-Multisets With Bounded Sum

Hard

#2583Time: O(N * r), where `N` is the length of `nums` and `r` is the upper bound of the sum range. The complexity arises from iterating through each distinct number and for each, iterating through its count and all possible sums up to `r`. A more precise bound is `O(r * sum(counts)) = O(r * N)`, which is too slow for the given constraints.Space: O(r), where `r` is the upper bound of the sum range. This is for the DP array.

Patterns

Sliding Window Dynamic Programming

Data structures

Array Hash Table

Prompt

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 10⁹+ 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}.

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 * 10⁴
0 <= nums[i] <= 2 * 10⁴
Sum of nums does not exceed 2 * 10⁴.
0 <= l <= r <= 2 * 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a straightforward dynamic programming method. It treats the problem as a bounded knapsack problem where each distinct number is an item type, its value and weight are the number itself, and the quantity is its frequency in the input array. We build a DP table dp[s] representing the number of ways to achieve a sum s. For each distinct number x with frequency c, we update the DP table by considering all possible counts (from 0 to c) of x to form new sums.

Algorithm

Count the frequency of each number in nums and store it in a map or an array called counts.
Handle the number 0 as a special case. The number of zeros, say z, multiplies the final count for any sum by z+1. We can solve the problem for non-zero numbers first and then apply this multiplier.
Initialize a DP array, dp, of size r+1. dp[s] will store the number of sub-multisets with sum s. Initialize dp[0] = 1 (for the empty set) and all other elements to 0.
Iterate through each distinct non-zero number x with its frequency c.
For each x, create a new DP array, next_dp. The value next_dp[s] is calculated by summing up dp[s - k*x] for k from 0 to c. This represents taking k copies of the number x.
After iterating through all distinct non-zero numbers, dp[s] will contain the number of ways to form sum s.
Sum the values in dp from index l to r to get the total count for the required range.
Multiply the result by (counts[0] + 1) to account for the sub-multisets formed using zeros.

Walkthrough

This method directly translates the problem into a dynamic programming solution. We first preprocess the nums array to get the frequency of each number. The core of the solution is a DP array, dp, where dp[s] stores the number of ways to form a sum s using the numbers processed so far.

We initialize dp[0] = 1 to represent the empty sub-multiset, which has a sum of 0. Then, we iterate through each distinct non-zero number x found in nums. Let's say x appears c times. To update our dp array for this number, we compute a next_dp array. The new number of ways to form a sum s, next_dp[s], is the sum of ways to form s - k*x using previous numbers, for all k from 0 to c. This is because we can choose to include k instances of x in our sub-multiset.

After iterating through all distinct non-zero numbers, the dp array is finalized. The number of sub-multisets with a sum in the range [l, r] is the sum of dp[s] for s from l to r. Finally, we account for the zeros. If there are z zeros in nums, they can be included in any sub-multiset in z+1 ways (taking 0, 1, ..., z zeros) without changing the sum. Thus, we multiply our calculated total by z+1.

1class Solution {2    public int countSubMultisets(java.util.List<Integer> nums, int l, int r) {3        final int MOD = 1_000_000_007;4        java.util.Map<Integer, Integer> counts = new java.util.HashMap<>();5        for (int num : nums) {6            counts.put(num, counts.getOrDefault(num, 0) + 1);7        }8 9        long[] dp = new long[r + 1];10        dp[0] = 1;11 12        for (java.util.Map.Entry<Integer, Integer> entry : counts.entrySet()) {13            int x = entry.getKey();14            int c = entry.getValue();15            if (x == 0) continue;16 17            long[] next_dp = new long[r + 1];18            for (int s = 0; s <= r; s++) {19                for (int k = 0; k <= c; k++) {20                    if (s - k * x >= 0) {21                        next_dp[s] = (next_dp[s] + dp[s - k * x]) % MOD;22                    } else {23                        break;24                    }25                }26            }27            dp = next_dp;28        }29 30        long ans = 0;31        for (int s = l; s <= r; s++) {32            ans = (ans + dp[s]) % MOD;33        }34 35        long zeroCount = counts.getOrDefault(0, 0);36        ans = (ans * (zeroCount + 1)) % MOD;37 38        return (int) ans;39    }40}

Complexity

Time

O(N * r), where `N` is the length of `nums` and `r` is the upper bound of the sum range. The complexity arises from iterating through each distinct number and for each, iterating through its count and all possible sums up to `r`. A more precise bound is `O(r * sum(counts)) = O(r * N)`, which is too slow for the given constraints.

Space

O(r), where `r` is the upper bound of the sum range. This is for the DP array.

Trade-offs

Pros

The logic is simple and directly models the problem statement.
It's a good starting point for understanding the problem's structure.

Cons

The time complexity is too high for the given constraints, leading to a 'Time Limit Exceeded' (TLE) error.
It requires O(r) extra space for the next_dp array in each iteration, although this can be optimized.

This approach significantly optimizes the DP transition from the naive solution. The key insight is that the inner loop in the naive DP, which calculates next_dp[s] = sum(dp[s - k*x]), can be replaced by a constant time calculation. This is achieved by recognizing the relationship dp_new[s] = dp_new[s-x] + dp_old[s] - dp_old[s - (c+1)*x]. This recurrence allows us to update the DP array for each distinct number in O(r) time, a massive improvement. This technique is sometimes known as a sliding window sum optimization applied to DP.

Algorithm

Count frequencies of numbers in nums into a map counts.
An important optimization: the maximum possible sum is the total sum of elements in nums. We can cap r at this total sum.
Initialize dp array of size r+1 with dp[0] = 1.
Handle zeros at the end by multiplying the final result by (counts[0] + 1).
For each distinct non-zero number x with count c:
- Pass 1 (Prefix Sums): Iterate s from x to r. Update dp[s] = (dp[s] + dp[s-x]) % MOD. This step calculates the number of ways to form sum s using an unlimited number of x's.
- Pass 2 (Correction): Iterate s from r down to (c+1)*x. Update dp[s] = (dp[s] - dp[s - (c+1)*x] + MOD) % MOD. This step corrects the counts by removing the combinations that used more than c copies of x.
After processing all distinct non-zero numbers, sum dp[s] for s from l to r.
Multiply the final sum by (counts[0] + 1) and return the result modulo 10^9 + 7.

Walkthrough

This optimized solution builds upon the same DP foundation but refines the state transition to be much more efficient. We still count frequencies and handle zeros at the end. The DP array dp[s] still represents the number of ways to make sum s.

The crucial improvement lies in how we update the dp array for each distinct non-zero number x with frequency c. Instead of a nested loop, we perform two passes over the dp array:

Prefix Sum Pass: We first iterate from s = x to r and update dp[s] by adding dp[s-x]. This is equivalent to calculating the number of ways to form each sum assuming we have an unlimited supply of x. After this pass, dp[s] stores the sum of dp_old[s], dp_old[s-x], dp_old[s-2x], and so on.
Correction Pass: The first pass overcounted by allowing more than c copies of x. We need to subtract these invalid combinations. A sub-multiset with sum s using more than c copies of x is equivalent to a sub-multiset with sum s - (c+1)*x combined with c+1 copies of x. The number of ways to do this is precisely the number of ways to form sum s - (c+1)*x with an unlimited supply of x, which is the value we computed in the first pass, i.e., the new dp[s - (c+1)*x]. So, we iterate s from r down to (c+1)*x and subtract dp[s - (c+1)*x]. The downward iteration is critical to ensure we use the values from the prefix sum pass before they are updated by the correction itself.

This two-pass update for each number reduces the complexity for processing one number type from O(r*c) to O(r), making the overall solution efficient enough to pass.

1class Solution {2    public int countSubMultisets(java.util.List<Integer> nums, int l, int r) {3        final int MOD = 1_000_000_007;4        java.util.Map<Integer, Integer> counts = new java.util.HashMap<>();5        int totalSum = 0;6        for (int num : nums) {7            counts.put(num, counts.getOrDefault(num, 0) + 1);8            totalSum += num;9        }10 11        r = Math.min(r, totalSum);12        if (l > r) {13            return 0;14        }15 16        long[] dp = new long[r + 1];17        dp[0] = 1;18 19        for (java.util.Map.Entry<Integer, Integer> entry : counts.entrySet()) {20            int x = entry.getKey();21            int c = entry.getValue();22            if (x == 0) continue;23 24            // Pass 1: Add contributions (unbounded knapsack style)25            for (int s = x; s <= r; s++) {26                dp[s] = (dp[s] + dp[s - x]) % MOD;27            }28 29            // Pass 2: Remove contributions of using more than c items30            int overLimit = (c + 1) * x;31            for (int s = r; s >= overLimit; s--) {32                dp[s] = (dp[s] - dp[s - overLimit] + MOD) % MOD;33            }34        }35 36        long ans = 0;37        for (int s = l; s <= r; s++) {38            ans = (ans + dp[s]) % MOD;39        }40 41        long zeroCount = counts.getOrDefault(0, 0);42        ans = (ans * (zeroCount + 1)) % MOD;43 44        return (int) ans;45    }46}

Complexity

Time

O(N + D * r), where `N` is `nums.length`, `D` is the number of distinct non-zero elements, and `r` is the sum upper bound. The number of distinct elements `D` is at most `O(sqrt(sum(nums)))`. Given the constraints, this is approximately `O(N + r * sqrt(r))`, which is very efficient.

Space

O(r), where `r` is the upper bound of the sum range. This is for the DP array and the frequency map.

Trade-offs

Pros

Highly efficient and passes the time limits for the given constraints.
Space-efficient due to the in-place update of the DP array.

Cons

The logic for the optimized DP transition is more complex and less intuitive than the naive approach.

Solutions

Solution

1class Solution {2  static final int MOD = 1_000_000_007;3public4  int countSubMultisets(List<Integer> nums, int l, int r) {5    Map<Integer, Integer> count = new HashMap<>();6    int total = 0;7    for (int num : nums) {8      total += num;9      if (num <= r) {10        count.merge(num, 1, Integer : : sum);11      }12    }13    if (total < l) {14      return 0;15    }16    r = Math.min(r, total);17    int[] dp = new int[r + 1];18    dp[0] = count.getOrDefault(0, 0) + 1;19    count.remove(Integer.valueOf(0));20    int sum = 0;21    for (Map.Entry<Integer, Integer> e : count.entrySet()) {22      int num = e.getKey();23      int c = e.getValue();24      sum = Math.min(sum + c * num, r);

1class Solution {2public:3  int countSubMultisets(const vector<int> &nums, int l, int r) {4    int cnt[20001] = {};5    int memo[20001] = {};6    const int mod = 1000000007;7    for (int n : nums) {8      ++cnt[n];9    }10    fill_n(memo, cnt[1] + 1, 1);11    for (int n = 2, total = cnt[1]; n <= r; ++n) {12      if (!cnt[n]) {13        continue;14      }15      int top = (cnt[n] + 1) * n;16      total += n * cnt[n];17      for (int i = n, ii = min(total, r); i <= ii; ++i) {18        memo[i] = (memo[i] + memo[i - n]) % mod;19      }20      for (int i = min(total, r); i >= top; --i) {21        memo[i] = (mod + memo[i] - memo[i - top]) % mod;22      }23    }24    return accumulate(memo + l, memo + r + 1, 0LL) * (cnt[0] + 1) % mod;25  }26};

1class Solution:2    # dp[i] := # 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 ]) % kMod3    def countSubMultisets(4        self, nums: List[int], l: int, r: int) -> int: kMod = 1_000_000_007

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem