和带限制的子多重集合的数目

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

/*
思路：
使用Java Stream的组合功能可以简洁地实现同样的功能。我们将动态规划数组转换为Stream进行计算。
*/
import java.util.stream.IntStream;

public class Solution {
    public int countSubsets(int[] nums, int l, int r) {
        int MOD = 1000000007;
        int maxSum = 20000; // 最大可能的和
        int[] dp = new int[maxSum + 1];
        dp[0] = 1; // 初始空集
        for (int num : nums) {
            for (int j = maxSum; j >= num; j--) {
                dp[j] = (dp[j] + dp[j - num]) % MOD;
            }
        }
        return IntStream.rangeClosed(l, r).map(i -> dp[i]).reduce(0, (a, b) -> (a + b) % MOD);
    }
}

此题解使用动态规划的方法解决问题。首先，它计算输入数组的总和 s，如果 s 小于 l，则直接返回 0。接着，它使用 Counter 来统计数组中每个元素的出现次数。动态规划数组 a 用于存储从和为 0 到 r 的子集的计数。a 的初始状态是 a[0] 等于 0 的元素的数量加 1。对于每个元素和其计数，更新动态规划数组 a，考虑包含不同数量的当前元素时的子集和。最终，根据 l 和 r 的值，计算和在 [l, r] 范围内的子集的数量并返回。

O(n * s)

O(r)