元宝 LeetCode 2902. 和带限制的子多重集合的数目 Java实现
这道题是 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 官方题解中的多重背包优化方法，在时间和空间上均达到较优水平。