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.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Dynamic Programming, Sliding Window
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^40 <= nums[i] <= 2 * 10^4Sum of nums does not exceed 2 * 10^40 <= l <= r <= 2 * 10^4
Hints for Count of Sub-Multisets With Bounded Sum
Hint 1
Group equal values: for a value
vthat occursctimes you only choose how many copies to take, 0 throughc.Hint 2
This is a bounded knapsack over sums up to
r. Because the total ofnumsis at most2 · 10^4, there are only about 200 distinct values.Hint 3
new[s] = old[s] + old[s - v] + … + old[s - c·v]is a sliding window along the residue class ofsmodv:new[s] = new[s - v] + old[s] - old[s - (c+1)·v]. Treat zeros separately — they multiply every count byc₀ + 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
- Count occurrences of each value. Pull out the zeros:
zcopies of 0 can be added to any sub-multiset inz + 1ways. - Let
dp[s]be the number of sub-multisets (of the values processed so far) with sums, fors ≤ r; start withdp[0] = 1. - For each positive value
v ≤ rwith countc, buildndwithnd[s] = dp[s]fors < vandnd[s] = nd[s - v] + dp[s] - dp[s - (c + 1)·v](the last term only when the index is non-negative), all modulo10^9 + 7. - Return
(z + 1) · (dp[l] + … + dp[r])modulo10^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 + 1factor. - 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) % MODJava
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