# Count of Sub-Multisets With Bounded Sum
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-of-sub-multisets-with-bounded-sum)
Canonical: https://scaleengineer.com/dsa/problems/count-of-sub-multisets-with-bounded-sum
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table
---
## Problem
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}.

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

# Approaches
## Naive Dynamic Programming
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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public int countSubMultisets(java.util.List<Integer> nums, int l, int r) {
        final int MOD = 1_000_000_007;
        java.util.Map<Integer, Integer> counts = new java.util.HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        long[] dp = new long[r + 1];
        dp[0] = 1;

        for (java.util.Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int x = entry.getKey();
            int c = entry.getValue();
            if (x == 0) continue;

            long[] next_dp = new long[r + 1];
            for (int s = 0; s <= r; s++) {
                for (int k = 0; k <= c; k++) {
                    if (s - k * x >= 0) {
                        next_dp[s] = (next_dp[s] + dp[s - k * x]) % MOD;
                    } else {
                        break;
                    }
                }
            }
            dp = next_dp;
        }

        long ans = 0;
        for (int s = l; s <= r; s++) {
            ans = (ans + dp[s]) % MOD;
        }

        long zeroCount = counts.getOrDefault(0, 0);
        ans = (ans * (zeroCount + 1)) % MOD;

        return (int) ans;
    }
}
```
### 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.

## Optimized Dynamic Programming
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.
**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.
**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.
### Explanation
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:

1.  **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.

2.  **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.

```java
class Solution {
    public int countSubMultisets(java.util.List<Integer> nums, int l, int r) {
        final int MOD = 1_000_000_007;
        java.util.Map<Integer, Integer> counts = new java.util.HashMap<>();
        int totalSum = 0;
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            totalSum += num;
        }

        r = Math.min(r, totalSum);
        if (l > r) {
            return 0;
        }

        long[] dp = new long[r + 1];
        dp[0] = 1;

        for (java.util.Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int x = entry.getKey();
            int c = entry.getValue();
            if (x == 0) continue;

            // Pass 1: Add contributions (unbounded knapsack style)
            for (int s = x; s <= r; s++) {
                dp[s] = (dp[s] + dp[s - x]) % MOD;
            }

            // Pass 2: Remove contributions of using more than c items
            int overLimit = (c + 1) * x;
            for (int s = r; s >= overLimit; s--) {
                dp[s] = (dp[s] - dp[s - overLimit] + MOD) % MOD;
            }
        }

        long ans = 0;
        for (int s = l; s <= r; s++) {
            ans = (ans + dp[s]) % MOD;
        }

        long zeroCount = counts.getOrDefault(0, 0);
        ans = (ans * (zeroCount + 1)) % MOD;

        return (int) ans;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
  static final int MOD = 1_000_000_007;
public
  int countSubMultisets(List<Integer> nums, int l, int r) {
    Map<Integer, Integer> count = new HashMap<>();
    int total = 0;
    for (int num : nums) {
      total += num;
      if (num <= r) {
        count.merge(num, 1, Integer : : sum);
      }
    }
    if (total < l) {
      return 0;
    }
    r = Math.min(r, total);
    int[] dp = new int[r + 1];
    dp[0] = count.getOrDefault(0, 0) + 1;
    count.remove(Integer.valueOf(0));
    int sum = 0;
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
      int num = e.getKey();
      int c = e.getValue();
      sum = Math.min(sum + c * num, r);
```

### CPP

```cpp
class Solution {
public:
  int countSubMultisets(const vector<int> &nums, int l, int r) {
    int cnt[20001] = {};
    int memo[20001] = {};
    const int mod = 1000000007;
    for (int n : nums) {
      ++cnt[n];
    }
    fill_n(memo, cnt[1] + 1, 1);
    for (int n = 2, total = cnt[1]; n <= r; ++n) {
      if (!cnt[n]) {
        continue;
      }
      int top = (cnt[n] + 1) * n;
      total += n * cnt[n];
      for (int i = n, ii = min(total, r); i <= ii; ++i) {
        memo[i] = (memo[i] + memo[i - n]) % mod;
      }
      for (int i = min(total, r); i >= top; --i) {
        memo[i] = (mod + memo[i] - memo[i - top]) % mod;
      }
    }
    return accumulate(memo + l, memo + r + 1, 0LL) * (cnt[0] + 1) % mod;
  }
};

```

### Python

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

```