✅☑[C++/C/Java/Python/JavaScript] || DP || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n1. Problem Context: The code aims to calculate the number of multisets with
# *PLEASE UPVOTE IF IT HELPED*\n\n---\n\n\n# Approaches\n***(Also explained in the code)***\n\n1. **Problem Context:** The code aims to calculate the number of multisets with sums within a specified range [l, r] for a given set of integers.\n\n1. **Initialization:**\n\n    - The code defines constants for modulo arithmetic (MOD) and the maximum number of elements (MAXN).\n    - It initializes an array `dp` to store dynamic programming values.\n\n1. **Dynamic Programming:**\n\n    - The code employs dynamic programming to compute the number of multisets efficiently.\n    - It initializes the `dp` array with zeros and sets `dp[0] = 1` as the base case for an empty set.\n1. **Sorting and Processing:**\n\n    - It sorts the input numbers in ascending order to handle duplicates more efficiently.\n    - The sorted array is reversed so that processing begins with the largest numbers.\n1. **Handling Leading Zeros:**\n\n    - The code checks and handles leading zeros in the sorted array.\n    - It increments dp[0] for each leading zero and removes these zeros from the array.\n1. **Iterating Through Unique Numbers:**\n\n- The code iterates through the sorted array and identifies unique numbers.\n- It counts the occurrences of each unique number and calculates a variable `chg` based on the sum of elements processed so far.\n1. **Counting Multisets:**\n\n    - It uses nested loops to count the number of multisets that contribute to each sum in the range [l, r].\n    - The inner loops handle various combinations of elements to achieve the target sum.\n    - The dynamic programming values are updated as the code progresses.\n1. **Final Result:**\n\n    - The code calculates the final result for the given range [l, r].\n    - It returns the result after applying modulo operation (MOD) to avoid integer overflow.\n\n\n\n\n# Complexity\n- **Time complexity:**\n   $$O(r * n^2)$$\n    (where \'r\' is the range and \'n\' is the number of unique elements.)\n\n- **Space complexity:**\n   $$O(MAXN)$$ \n(The space complexity is constant since the \'dp\' array has a fixed size)\n    \n\n\n# Code\n```C++ []\nclass Solution {\n    const int MOD = 1000000007; // Define a constant for modulo arithmetic.\n    const int MAXN = 20000; // Define a constant for the maximum number of elements in the array.\n\n    int dp[20005]; // Initialize an array to store dynamic programming values.\n\npublic:\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        for (int i = 0; i <= r; i++) {\n            dp[i] = 0; // Initialize the DP array with zeros.\n        }\n        dp[0] = 1; // The base case for an empty set is 1.\n\n        sort(nums.begin(), nums.end()); // Sort the input numbers in ascending order.\n        reverse(nums.begin(), nums.end()); // Reverse the sorted array to start with the largest numbers.\n        int sf = 0; // Initialize a variable to keep track of the sum of elements.\n\n        // Handle leading zeros in the sorted array.\n        while (nums.size() && nums.back() == 0) {\n            dp[0]++;\n            nums.pop_back(); // Remove leading zeros.\n        }\n\n        // Process the sorted array.\n        while (nums.size()) {\n            int tt = nums.back(); // Get the next unique number.\n            int cn = 0; // Initialize a counter for this number.\n            while (nums.size() && nums.back() == tt) {\n                nums.pop_back();\n                cn++; // Count the occurrences of the current number.\n            }\n\n            int chg = min(sf + tt * cn, r); // Calculate the change variable based on the sum so far.\n            for (int i = chg; i >= tt; i--) {\n                for (int j = 1; j <= cn && i - (j * tt) >= 0; j++) {\n                    dp[i] += dp[i - j * tt]; // Calculate the number of subsets for the current sum.\n                    if (dp[i] >= MOD) dp[i] -= MOD; // Apply modulo operation.\n                }\n            }\n\n            sf += tt * cn; // Update the sum so far.\n        }\n\n        int ans = 0;\n        for (int i = l; i <= r; i++) {\n            ans += dp[i]; // Calculate the answer by summing the DP values within the given range.\n            ans %= MOD; // Apply modulo operation to the final answer.\n        }\n\n        return ans;\n    }\n};\n\n\n```\n```C []\n#include <stdio.h>\n#include <stdlib.h>\n\nconst int MOD = 1000000007;\nconst int MAXN = 20000;\n\nint dp[20005];\n\nvoid reverseArray(int arr[], int n) {\n    int start = 0;\n    int end = n - 1;\n    while (start < end) {\n        int temp = arr[start];\n        arr[start] = arr[end];\n        arr[end] = temp;\n        start++;\n        end--;\n    }\n}\n\nvoid removeLastElement(int arr[], int *n) {\n    if (*n > 0) {\n        int *newArr = (int *)malloc((*n - 1) * sizeof(int));\n        for (int i = 0; i < *n - 1; i++) {\n            newArr[i] = arr[i];\n        }\n        free(arr);\n        arr = newArr;\n        (*n)--;\n    }\n}\n\nint countSubMultisets(int nums[], int n, int l, int r) {\n    for (int i = 0; i <= r; i++) {\n        dp[i] = 0;\n    }\n    dp[0] = 1;\n\n    reverseArray(nums, n);\n\n    int sf = 0;\n\n    while (n > 0 && nums[n - 1] == 0) {\n        dp[0]++;\n        removeLastElement(nums, &n);\n    }\n\n    while (n > 0) {\n        int tt = nums[n - 1];\n        int cn = 0;\n        while (n > 0 && nums[n - 1] == tt) {\n            removeLastElement(nums, &n);\n            cn++;\n        }\n\n        int chg = (sf + tt * cn) < r ? (sf + tt * cn) : r;\n        for (int i = chg; i >= tt; i--) {\n            for (int j = 1; j <= cn && (i - (j * tt)) >= 0; j++) {\n                dp[i] += dp[i - j * tt];\n                if (dp[i] >= MOD) dp[i] -= MOD;\n            }\n        }\n\n        sf += tt * cn;\n    }\n\n    int ans = 0;\n    for (int i = l; i <= r; i++) {\n        ans += dp[i];\n        ans %= MOD;\n    }\n\n    return ans;\n}\n\n```\n```Java []\npublic class Solution {\n    private final int MOD = 1000000007;\n    private final int MAXN = 20000;\n    private int[] dp = new int[20005];\n\n    public int countSubMultisets(int[] nums, int l, int r) {\n        for (int i = 0; i <= r; i++) {\n            dp[i] = 0;\n        }\n        dp[0] = 1;\n\n        Arrays.sort(nums);\n        reverseArray(nums);\n        int sf = 0;\n\n        while (nums.length > 0 && nums[nums.length - 1] == 0) {\n            dp[0]++;\n            removeLastElement(nums);\n        }\n\n        while (nums.length > 0) {\n            int tt = nums[nums.length - 1];\n            int cn = 0;\n            while (nums.length > 0 && nums[nums.length - 1] == tt) {\n                removeLastElement(nums);\n                cn++;\n            }\n\n            int chg = Math.min(sf + tt * cn, r);\n            for (int i = chg; i >= tt; i--) {\n                for (int j = 1; j <= cn && i - (j * tt) >= 0; j++) {\n                    dp[i] += dp[i - j * tt];\n                    if (dp[i] >= MOD) {\n                        dp[i] -= MOD;\n                    }\n                }\n            }\n\n            sf += tt * cn;\n        }\n\n        int ans = 0;\n        for (int i = l; i <= r; i++) {\n            ans += dp[i];\n            ans %= MOD;\n        }\n\n        return ans;\n    }\n\n    private void reverseArray(int[] arr) {\n        int start = 0;\n        int end = arr.length - 1;\n        while (start < end) {\n            int temp = arr[start];\n            arr[start] = arr[end];\n            arr[end] = temp;\n            start++;\n            end--;\n        }\n    }\n\n    private void removeLastElement(int[] arr) {\n        if (arr.length > 0) {\n            int[] newArr = new int[arr.length - 1];\n            for (int i = 0; i < newArr.length; i++) {\n                newArr[i] = arr[i];\n            }\n            arr = newArr;\n        }\n    }\n}\n\n```\n```python3 []\n\nclass Solution:\n    MOD = 1000000007\n    MAXN = 20000\n\n    def __init__(self):\n        self.dp = [0] * 20005\n\n    def countSubMultisets(self, nums, l, r):\n        for i in range(r + 1):\n            self.dp[i] = 0\n        self.dp[0] = 1\n\n        nums.sort()\n        nums.reverse()\n        sf = 0\n\n        while nums and nums[-1] == 0:\n            self.dp[0] += 1\n            nums.pop()\n\n        while nums:\n            tt = nums[-1]\n            cn = 0\n            while nums and nums[-1] == tt:\n                nums.pop()\n                cn += 1\n\n            chg = min(sf + tt * cn, r)\n            for i in range(chg, tt - 1, -1):\n                for j in range(1, cn + 1):\n                    if i - (j * tt) >= 0:\n                        self.dp[i] += self.dp[i - j * tt]\n                        if self.dp[i] >= self.MOD:\n                            self.dp[i] -= self.MOD\n\n            sf += tt * cn\n\n        ans = 0\n        for i in range(l, r + 1):\n            ans += self.dp[i]\n            ans %= self.MOD\n\n        return ans\n\n\n```\n```javascript []\n\nclass Solution {\n    constructor() {\n        this.MOD = 1000000007;\n        this.MAXN = 20000;\n        this.dp = new Array(20005).fill(0);\n    }\n\n    countSubMultisets(nums, l, r) {\n        for (let i = 0; i <= r; i++) {\n            this.dp[i] = 0;\n        }\n        this.dp[0] = 1;\n\n        nums.sort((a, b) => a - b);\n        nums.reverse();\n        let sf = 0;\n\n        while (nums.length > 0 && nums[nums.length - 1] === 0) {\n            this.dp[0]++;\n            nums.pop();\n        }\n\n        while (nums.length > 0) {\n            const tt = nums[nums.length - 1];\n            let cn = 0;\n            while (nums.length > 0 && nums[nums.length - 1] === tt) {\n                nums.pop();\n                cn++;\n            }\n\n            const chg = Math.min(sf + tt * cn, r);\n            for (let i = chg; i >= tt; i--) {\n                for (let j = 1; j <= cn; j++) {\n                    if (i - j * tt >= 0) {\n                        this.dp[i] += this.dp[i - j * tt];\n                        if (this.dp[i] >= this.MOD) {\n                            this.dp[i] -= this.MOD;\n                        }\n                    }\n                }\n            }\n\n            sf += tt * cn;\n        }\n\n        let ans = 0;\n        for (let i = l; i <= r; i++) {\n            ans += this.dp[i];\n            ans %= this.MOD;\n        }\n\n        return ans;\n    }\n}\n\n\n\n```\n---\n\n\n# *PLEASE UPVOTE IF IT HELPED*\n\n---\n---\n\n\n---\n\n
['Dynamic Programming', 'C', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']