Problem

You are given a 0-indexed array nums of non-negative integers, and two integers l and r.

Return thecount 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^9 + 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.

Examples

Example 1

1
2
3

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

1
2
3

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

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

Solution

Method 1 – Dynamic Programming with Bounded Knapsack

Intuition

This is a variation of the bounded knapsack problem. For each unique value in nums, we can use it up to its frequency. We use dynamic programming to count the number of multisets (with repetitions up to the frequency) whose sum is in [l, r].

Approach

  1. Count the frequency of each unique value in nums.
  2. Let dp[s] be the number of ways to form sum s using the available numbers.
  3. Initialize dp[0] = 1 (empty multiset).
  4. For each unique value and its count:
    • Use a temporary array to update dp for each possible number of times the value can be used (from 1 to count), using a sliding window to optimize.
  5. After processing all values, sum dp[s] for s in [l, r].
  6. Return the answer modulo 10^9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int countSubMultisets(vector<int>& nums, int l, int r) {
        const int MOD = 1e9+7;
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;
        vector<int> dp(r+1, 0); dp[0] = 1;
        for (auto& [val, cnt] : freq) {
            vector<int> ndp = dp;
            for (int rem = 1; rem <= cnt; ++rem) {
                for (int s = r; s >= val*rem; --s) {
                    ndp[s] = (ndp[s] + dp[s - val*rem]) % MOD;
                }
            }
            dp = ndp;
        }
        int ans = 0;
        for (int s = l; s <= r; ++s) ans = (ans + dp[s]) % MOD;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func CountSubMultisets(nums []int, l, r int) int {
    MOD := 1_000_000_007
    freq := map[int]int{}
    for _, x := range nums {
        freq[x]++
    }
    dp := make([]int, r+1)
    dp[0] = 1
    for val, cnt := range freq {
        ndp := make([]int, len(dp))
        copy(ndp, dp)
        for rem := 1; rem <= cnt; rem++ {
            for s := r; s >= val*rem; s-- {
                ndp[s] = (ndp[s] + dp[s-val*rem]) % MOD
            }
        }
        dp = ndp
    }
    ans := 0
    for s := l; s <= r; s++ {
        ans = (ans + dp[s]) % MOD
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int countSubMultisets(int[] nums, int l, int r) {
        int MOD = 1_000_000_007;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        int[] dp = new int[r+1]; dp[0] = 1;
        for (var e : freq.entrySet()) {
            int val = e.getKey(), cnt = e.getValue();
            int[] ndp = dp.clone();
            for (int rem = 1; rem <= cnt; rem++) {
                for (int s = r; s >= val*rem; s--) {
                    ndp[s] = (ndp[s] + dp[s - val*rem]) % MOD;
                }
            }
            dp = ndp;
        }
        int ans = 0;
        for (int s = l; s <= r; s++) ans = (ans + dp[s]) % MOD;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun countSubMultisets(nums: IntArray, l: Int, r: Int): Int {
        val MOD = 1_000_000_007
        val freq = nums.groupingBy { it }.eachCount()
        var dp = IntArray(r+1); dp[0] = 1
        for ((val_, cnt) in freq) {
            val ndp = dp.copyOf()
            for (rem in 1..cnt) {
                for (s in r downTo val_ * rem) {
                    ndp[s] = (ndp[s] + dp[s - val_ * rem]) % MOD
                }
            }
            dp = ndp
        }
        var ans = 0
        for (s in l..r) ans = (ans + dp[s]) % MOD
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def countSubMultisets(self, nums: list[int], l: int, r: int) -> int:
        MOD = 10**9 + 7
        from collections import Counter
        freq = Counter(nums)
        dp = [0] * (r+1)
        dp[0] = 1
        for val, cnt in freq.items():
            ndp = dp[:]
            for rem in range(1, cnt+1):
                for s in range(r, val*rem-1, -1):
                    ndp[s] = (ndp[s] + dp[s - val*rem]) % MOD
            dp = ndp
        return sum(dp[s] for s in range(l, r+1)) % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn count_sub_multisets(nums: Vec<i32>, l: i32, r: i32) -> i32 {
        let m = 1_000_000_007;
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for &x in &nums { *freq.entry(x).or_insert(0) += 1; }
        let mut dp = vec![0; (r+1) as usize]; dp[0] = 1;
        for (&val, &cnt) in freq.iter() {
            let mut ndp = dp.clone();
            for rem in 1..=cnt {
                for s in (val*rem..=r).rev() {
                    ndp[s as usize] = (ndp[s as usize] + dp[(s - val*rem) as usize]) % m;
                }
            }
            dp = ndp;
        }
        let mut ans = 0;
        for s in l..=r { ans = (ans + dp[s as usize]) % m; }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    countSubMultisets(nums: number[], l: number, r: number): number {
        const MOD = 1_000_000_007;
        const freq = new Map<number, number>();
        for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
        let dp = Array(r+1).fill(0); dp[0] = 1;
        for (const [val, cnt] of freq.entries()) {
            const ndp = dp.slice();
            for (let rem = 1; rem <= cnt; rem++) {
                for (let s = r; s >= val*rem; s--) {
                    ndp[s] = (ndp[s] + dp[s - val*rem]) % MOD;
                }
            }
            dp = ndp;
        }
        let ans = 0;
        for (let s = l; s <= r; s++) ans = (ans + dp[s]) % MOD;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * r), where n is the number of unique values and r is the upper bound for the sum. For each value, we update the dp array up to r for each count.
  • 🧺 Space complexity: O(r), for the dp array.