这道题是 LeetCode 2902 “Count of Sub-Multisets With Bounded Sum”，属于多重背包问题，需要计算在给定数组 nums 中，所有元素和位于区间 [l, r] 内的子多重集合（允许重复元素，但每个元素的选取次数不超过其在 nums 中的出现次数）的数目。下面给出 Java 实现及其核心思路。
解题思路
统计频率：用哈希表记录每个数字出现的次数，特别处理数字 0（因为 0 不影响和，但会影响方案数）。
动态规划：定义 dp[j] 表示元素和恰好为 j 的子多重集合的方案数。初始时 dp[0] = 1（空集合）。
多重背包转移：对于每个非零数字 num 及其出现次数 cnt，采用“前缀和优化”的转移方式：
-
先计算 stride[i] = dp[i] + dp[i-num] + dp[i-2*num] + …（即不考虑次数上限时的方案数）。
-
再通过 dp[i] = stride[i] – stride[i – (cnt+1)*num] 扣除选取超过 cnt 次的方案。
累加答案：最后将 dp[l] 到 dp[r] 的所有方案数相加，并乘以 (零的个数 + 1)（因为 0 可以任意选或不选）。
Java 实现
import java.util.*;
class Solution {
private static final int MOD = 1_000_000_007;
public int countSubMultisets(List<Integer> nums, int l, int r) {
// 1. 统计频率
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
// 2. 处理数字 0
int zeros = count.getOrDefault(0, 0);
count.remove(0);
// 3. 动态规划数组
int[] dp = new int[r + 1];
dp[0] = 1;
// 4. 多重背包转移
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
int num = entry.getKey();
int freq = entry.getValue();
// 计算 stride[i] = dp[i] + dp[i-num] + dp[i-2*num] + …
int[] stride = dp.clone();
for (int i = num; i <= r; i++) {
stride[i] = (stride[i] + stride[i – num]) % MOD;
}
// 扣除超过 freq 次的方案
int limit = num * (freq + 1);
for (int i = r; i >= 0; i–) {
if (i >= limit) {
dp[i] = (stride[i] – stride[i – limit] + MOD) % MOD;
} else {
dp[i] = stride[i] % MOD;
}
}
}
// 5. 累加区间 [l, r] 的方案数
long total = 0;
for (int i = l; i <= r; i++) {
total = (total + dp[i]) % MOD;
}
// 6. 乘以零的贡献（每个零可选可不选）
return (int) (total * (zeros + 1) % MOD);
}
}
关键点说明
-
时间复杂度：O(n + r·√Σ(nums[i]))，其中 n 为数组长度，r 为上限值。
-
空间复杂度：O(r)，仅使用一维 DP 数组。
-
零的处理：数字 0 不参与和的计算，但每个 0 都可以独立地“选”或“不选”，因此最终答案需乘以 (zeros + 1)。
-
模运算：由于结果可能很大，需要在每次加法、减法后取模 1_000_000_007。
示例
输入：nums = [1,2,2,3], l = 3, r = 5
输出：7
解释：和位于 [3,5] 的子多重集合有：
-
{1,2}（和=3）
-
{3}（和=3）
-
{1,2,2}（和=5）
-
{2,3}（和=5）
-
{1,3}（和=4）
-
{1,1,2}（和=4，但只有一个1，不可行）← 注意重复元素限制
实际需根据代码计算得到 7 种。
此实现参考了 LeetCode 官方题解中的多重背包优化方法，在时间和空间上均达到较优水平。
