2902

2902. Count of Sub-Multisets With Bounded Sum (Hard)

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 109 + 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.

 

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

Related Topics:
Array, Hash Table, Dynamic Programming, Sliding Window

Similar Questions:

• Coin Change (Medium)
• Coin Change II (Medium)

Hints:

• Since the sum of numsis at most 20000, the number of distinct elements of nums is 200.
• Let dp[x] be the number of submultisets of nums with sum x.
• The answer to the problem is dp[l] + dp[l+1] + … + dp[r].
• Use coin change dp to transition between states.

Solution 1.

What's the max number of distinct elements in A? To get the max number of distinct elements, we fill 0,1,2,... into A, and the sum is (N-1)*N/2. Since the sum of A is at most 20000, we can get that the max number of N is 200.

Let dp[x] be the number of submultisets of A with sum x. The answer is SUM( dp[i] | l <= i <= r ).

We can calculate dp[x] using bounded knapsack.

dp[i+1][0] = 1
dp[i+1][x] = dp[i][x] // don't use A[i]
				+ dp[i][x-A[i]] // use A[i] once
				+ dp[i][x-2*A[i]] // use A[i] twice
				+ ...
				+ dp[i][x-cnt[i]*A[i]] // use A[i] `cnt[i]` times where cnt[i] is the count of A[i] in the original array

Since dp[i+1][x] only depends on values in the previous row, we can reduce the space complexity to O(2*N)

next[x] = dp[x] + dp[x-A[i]] + ... dp[x-cnt[i]*A[i]]
		= dp[x] + next[x-A[i]] - dp[x-(cnt[i]+1)*A[i]]

// OJ: https://leetcode.com/problems/count-of-sub-multisets-with-bounded-sum
// Author: github.com/lzl124631x
// Time: O(N + UR) where U is the number of unique numbers in `A`
// Space: O(U + R)
class Solution {
public:
    int countSubMultisets(vector<int>& A, int L, int R) {
        long N = A.size(), mod = 1e9 + 7, ans = 0;
        unordered_map<int, int> cnt;
        for (int n : A) cnt[n]++;
        vector<long> dp(R + 1);
        dp[0] = 1;
        for (auto &[n, c] : cnt) {
            if (n == 0) continue;
            vector<long> next(R + 1);
            next[0] = 1;
            for (int x = 1; x <= R; ++x) {
                next[x] = dp[x];
                if (x - n >= 0) {
                    next[x] = (next[x] + next[x - n]) % mod;
                    if (x - (c + 1) * n >= 0) next[x] = (next[x] - dp[x - (c + 1) * n] + mod) % mod;
                }
            }
            swap(dp, next);
        }
        for (int i = L; i <= R; ++i) ans = (ans + dp[i]) % mod;
        return ans * (cnt[0] + 1) % mod;
    }
};