Count of Sub-Multisets With Bounded Sum
HardUpdated: Jul 26, 2025
Practice on:
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
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^40 <= nums[i] <= 2 * 10^4- Sum of
numsdoes not exceed2 * 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
- Count the frequency of each unique value in nums.
- Let dp[s] be the number of ways to form sum s using the available numbers.
- Initialize dp[0] = 1 (empty multiset).
- 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.
- After processing all values, sum dp[s] for s in [l, r].
- Return the answer modulo 10^9+7.
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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.