Count of sub multisets with bounded sum

Array Hash Table Dynamic Programming Sliding Window

22.2% acceptance

Feb 25, 2026

163

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

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_sub_multisets(nums: Vec<i32>, l: i32, r: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let total_sum: i32 = nums.iter().sum();
    if total_sum < l { return 0; }
    let r = r.min(total_sum) as usize;
    let l = l as usize;

    let mut freq = std::collections::HashMap::<i32, usize>::new();
    for &x in &nums {
      *freq.entry(x).or_default() += 1;
    }
    let zero_count = *freq.get(&0).unwrap_or(&0) as i64;

    let mut dp = vec![0i64; r + 1];
    dp[0] = 1;

    for (&v, &cnt) in &freq {
      if v == 0 { continue; }
      let v = v as usize;
      let mut ndp = vec![0i64; r + 1];
      for rem in 0..v.min(r + 1) {
        let mut window_sum = 0i64;
        let mut window_start = 0usize; // tracks the index of oldest window element
        let mut t = 0usize;
        loop {
          let idx = rem + t * v;
          if idx > r { break; }
          window_sum = (window_sum + dp[idx]) % MOD;
          // window has t - window_start + 1 elements; max allowed is cnt+1
          if t >= cnt + window_start + 1 {
            let old_idx = rem + window_start * v;
            window_sum = (window_sum - dp[old_idx] + MOD) % MOD;
            window_start += 1;
          }
          ndp[idx] = window_sum;
          t += 1;
        }
      }
      dp = ndp;
    }

    let mut ans = 0i64;
    for i in l..=r {
      ans = (ans + dp[i]) % MOD;
    }
    ans = ans * (zero_count + 1) % MOD;
    ans as i32
  }
}