Count of Sub-Multisets With Bounded Sum

Hard
1641.

Count of Sub-Multisets With Bounded Sum

Count of Sub-Multisets With Bounded Sum is a hard coding problem on arrays, hash table and dynamic programming, asked in Google interviews.

You are given an array nums of non-negative integers and two integers l and r.

A sub-multiset of nums is an unordered collection in which each value x appears between 0 and occ[x] times, where occ[x] is how often x occurs in nums. Two sub-multisets are the same if every value appears the same number of times in both — which positions the copies came from does not matter. The empty collection is a sub-multiset with sum 0.

Return the number of sub-multisets whose sum lies in the inclusive range [l, r]. Since the answer may be large, return it modulo 10^9 + 7.

Example 1

Input
nums = [1,2,2,3], l = 6, r = 6
Output
1
Explanation
Only {1, 2, 3} sums to 6. Using either copy of 2 gives the same sub-multiset.

Example 2

Input
nums = [2,1,4,2,7], l = 1, r = 5
Output
7
Explanation
{1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4} and {1, 2, 2}.

Example 3

Input
nums = [0,0,3], l = 0, r = 0
Output
3
Explanation
The empty collection, {0} and {0, 0} all sum to 0.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} l
 * @param {number} r
 * @return {number}
 */
var countSubMultisets = function(nums, l, r) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count of Sub-Multisets With Bounded Sum — Problem & Solution

Count of Sub-Multisets With Bounded Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count of Sub-Multisets With Bounded Sum is a hard coding problem on arrays, hash table and dynamic programming, asked in Google interviews.

Problem statement

You are given an array nums of non-negative integers and two integers l and r.

A sub-multiset of nums is an unordered collection in which each value x appears between 0 and occ[x] times, where occ[x] is how often x occurs in nums. Two sub-multisets are the same if every value appears the same number of times in both — which positions the copies came from does not matter. The empty collection is a sub-multiset with sum 0.

Return the number of sub-multisets whose sum lies in the inclusive range [l, r]. Since the answer may be large, return it modulo 10^9 + 7.

Example 1

Input: nums = [1,2,2,3], l = 6, r = 6
Output: 1
Explanation: Only {1, 2, 3} sums to 6. Using either copy of 2 gives the same sub-multiset.

Example 2

Input: nums = [2,1,4,2,7], l = 1, r = 5
Output: 7
Explanation: {1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4} and {1, 2, 2}.

Example 3

Input: nums = [0,0,3], l = 0, r = 0
Output: 3
Explanation: The empty collection, {0} and {0, 0} all sum to 0.

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

Hints for Count of Sub-Multisets With Bounded Sum

  1. Hint 1

    Group equal values: for a value v that occurs c times you only choose how many copies to take, 0 through c.

  2. Hint 2

    This is a bounded knapsack over sums up to r. Because the total of nums is at most 2 · 10^4, there are only about 200 distinct values.

  3. Hint 3

    new[s] = old[s] + old[s - v] + … + old[s - c·v] is a sliding window along the residue class of s mod v: new[s] = new[s - v] + old[s] - old[s - (c+1)·v]. Treat zeros separately — they multiply every count by c₀ + 1.

How to solve Count of Sub-Multisets With Bounded Sum

Counting sub-multisets is a bounded knapsack over distinct values. Because the sum of nums is at most 2 · 10^4, there are at most about 200 distinct positive values, and each can be folded into the DP in O(r) with a sliding-window sum.

Approach

  1. Count occurrences of each value. Pull out the zeros: z copies of 0 can be added to any sub-multiset in z + 1 ways.
  2. Let dp[s] be the number of sub-multisets (of the values processed so far) with sum s, for s ≤ r; start with dp[0] = 1.
  3. For each positive value v ≤ r with count c, build nd with nd[s] = dp[s] for s < v and nd[s] = nd[s - v] + dp[s] - dp[s - (c + 1)·v] (the last term only when the index is non-negative), all modulo 10^9 + 7.
  4. Return (z + 1) · (dp[l] + … + dp[r]) modulo 10^9 + 7.

Why it works

nd[s] must equal dp[s] + dp[s - v] + … + dp[s - c·v] — the ways to reach s after choosing 0 to c copies of v. nd[s - v] is the same window shifted one step down, so adding dp[s] and dropping dp[s - (c+1)·v] slides it. Zeros never change a sum, so they only multiply the count.

Complexity

  • Time — O(r · √S) where S is the sum of nums (the number of distinct values)
  • Space — O(r)

Pitfalls

  • Do not treat equal values as distinct items — {2} from either copy of 2 is one sub-multiset.
  • Zeros break the sliding window (a step of 0); handle them with the z + 1 factor.
  • Subtraction under a modulus can go negative — add the modulus back before taking the remainder.

Reference solution

Python

from typing import List

def countSubMultisets(nums: List[int], l: int, r: int) -> int:
    MOD = 10**9 + 7
    cnt = {}
    for v in nums:
        cnt[v] = cnt.get(v, 0) + 1
    zeros = cnt.pop(0, 0)
    dp = [0] * (r + 1)
    dp[0] = 1
    for v, c in cnt.items():
        if v > r:
            continue
        nd = dp[:]
        span = (c + 1) * v
        for s in range(v, r + 1):
            val = nd[s - v] + dp[s]
            if s >= span:
                val -= dp[s - span]
            nd[s] = val % MOD
        dp = nd
    return (zeros + 1) * (sum(dp[l:r + 1]) % MOD) % MOD

Java

public static int countSubMultisets(int[] nums, int l, int r) {
    final long MOD = 1000000007L;
    int maxV = 0;
    for (int v : nums) maxV = Math.max(maxV, v);
    int[] cnt = new int[maxV + 1];
    for (int v : nums) cnt[v]++;
    long[] dp = new long[r + 1];
    dp[0] = 1;
    for (int v = 1; v <= maxV && v <= r; v++) {
        int c = cnt[v];
        if (c == 0) continue;
        long[] nd = dp.clone();
        long span = (long) (c + 1) * v;
        for (int s = v; s <= r; s++) {
            long val = nd[s - v] + dp[s];
            if (s >= span) val -= dp[(int) (s - span)];
            nd[s] = ((val % MOD) + MOD) % MOD;
        }
        dp = nd;
    }
    long total = 0;
    for (int s = l; s <= r; s++) total = (total + dp[s]) % MOD;
    return (int) ((cnt[0] + 1) * total % MOD);
}

C++

int countSubMultisets(vector<int>& nums, int l, int r) {
    const long long MOD = 1000000007LL;
    int maxV = 0;
    for (int v : nums) maxV = max(maxV, v);
    vector<int> cnt(maxV + 1, 0);
    for (int v : nums) cnt[v]++;
    vector<long long> dp(r + 1, 0);
    dp[0] = 1;
    for (int v = 1; v <= maxV && v <= r; v++) {
        int c = cnt[v];
        if (c == 0) continue;
        vector<long long> nd = dp;
        long long span = (long long) (c + 1) * v;
        for (int s = v; s <= r; s++) {
            long long val = nd[s - v] + dp[s];
            if (s >= span) val -= dp[s - span];
            nd[s] = ((val % MOD) + MOD) % MOD;
        }
        dp = nd;
    }
    long long total = 0;
    for (int s = l; s <= r; s++) total = (total + dp[s]) % MOD;
    return (int) ((cnt[0] + 1) * total % MOD);
}

JavaScript

var countSubMultisets = function(nums, l, r) {
    var MOD = 1000000007;
    var maxV = 0;
    for (var i = 0; i < nums.length; i++) if (nums[i] > maxV) maxV = nums[i];
    var cnt = new Array(maxV + 1).fill(0);
    for (var i = 0; i < nums.length; i++) cnt[nums[i]]++;
    var dp = new Array(r + 1).fill(0);
    dp[0] = 1;
    for (var v = 1; v <= maxV && v <= r; v++) {
        var c = cnt[v];
        if (c === 0) continue;
        var nd = dp.slice();
        var span = (c + 1) * v;
        for (var s = v; s <= r; s++) {
            var val = nd[s - v] + dp[s];
            if (s >= span) val -= dp[s - span];
            nd[s] = ((val % MOD) + MOD) % MOD;
        }
        dp = nd;
    }
    var total = 0;
    for (var s = l; s <= r; s++) total = (total + dp[s]) % MOD;
    return ((cnt[0] + 1) * total) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets