LeetCode 2902: Count of Sub-Multisets With Bounded Sum

Explanation

To solve this problem, we can use dynamic programming. We will iterate through each element in the input array nums and for each element, we will calculate the count of sub-multisets that fall within the range [l, r] considering that element. We will maintain a 2D array dp where dp[i][j] represents the count of sub-multisets whose sum is j considering the first i elements of the input array.

At each step, we will update the dp array based on the current element being considered. To calculate the count of sub-multisets for the current element, we will consider two cases: including the current element in the subset and excluding the current element from the subset.

Finally, we will sum up the counts for all possible sums within the range [l, r] to get the total count of valid sub-multisets.

Time Complexity: O(n * (r-l+1)) where n is the length of the input array nums and (r-l+1) is the range of sums.

Space Complexity: O(n * (r-l+1)) for the dp array.

class Solution {
    public int countSubsets(int[] nums, int l, int r) {
        int mod = 1000000007;
        int n = nums.length;
        int[][] dp = new int[n + 1][r - l + 2];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= r - l + 1; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - nums[i - 1] + l]) % mod;
            }
        }

        int count = 0;
        for (int j = Math.max(0, l); j <= r; j++) {
            count = (count + dp[n][j - l]) % mod;
        }

        return count;
    }
}