Read this if you couldn't understand from any other solution. Comment if you still have a doubt.
Intuition\n Describe your first thoughts on how to solve this problem. \nI am assuming that you can solve question the simpler version of the problem where all 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI am assuming that you can solve question the simpler version of the problem where all elements of the array are unique via dynamic programming considering the cases of picking or not picking the elements as we traverse the array, if not then first go and solve coin change II on leetcode. Now in this problem the change is that instead of considering whether to pick or not pick some number, we need to consider how many of that number should we pick. Also, we will handle zeroes separately as the logic we will use in the DP transitions will be inefficient with zeroes. If by ignoring the zeroes you get the answer $$ans$$, then the answer with zeroes is just $$ans*(1 + occ[0])$$, as in every set we can have either no zeroes, one zero, two zero, ... or $occ[0]$ zeroes.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSince our recursion logic requires us to decide how many of a number to pick, we should make that decision for every number for which we need to have a count of all the unique elements ready to be traversed for populating the table. We store this in an `unordered_map<int,int> count`. Now we can traverse this map with the following transition:\n```\nfor(int j = 0;j<=r;j++){\n    for(int k=0;k<=freq and j>=k*num;k++){\n        dp[idx][j] = (dp[idx][j] + dp[idx-1][j-k*num])%mod; \n    }\n}\n```\nHere `dp[idx][j]` stores the number of sub-multisets with sum `j` while considering only the first `1+idx` elements of the `count` map. In this transition we are computing number of ways to sum upto `j` till index `idx` by summing up the number of ways when we are picking the current element `k` times, where `k` varies from `0` to the count of the element or the maximum number of times we can pick the element, whichever is smaller. This solutio is correct, but it will give TLE.\n\nNow we consider three cases (`num` is the current element and `freq` it\'s frequency)\n1. `(1+freq)*num <= j`:\nNotice here that, \n```\ndp[idx][j] = dp[idx-1][j] + dp[idx-1][j-num] + dp[idx-1][j-2*num] ... dp[idx-1][j - freq*num]\n\nand\n\ndp[idx][j-num] = dp[idx-1][j-num] + dp[idx-1][j-2*num] ... dp[idx-1][j - freq*num] + dp[idx-1][j - (1+freq)*num]\n\nso\n\ndp[idx][j] = dp[idx-1][j] + dp[idx][j-num] - dp[idx-1][j - (1+freq)*num]\n```\n\n2. Not 1. but `num <= j`:\nIn this case, since 1. is not true, let `p` be the maximum natural number such that `p*num <= j`, then:\n```\ndp[idx][j] = p[idx-1][j] + dp[idx-1][j-num] + dp[idx-1][j-2*num] ... dp[idx-1][j - p*num]\n\nand\n\ndp[idx][j-num] = dp[idx-1][j-num] + dp[idx-1][j-2*num] ...  + dp[idx-1][j - p*num]\n\nso\n\ndp[idx][j] = dp[idx-1][j] + dp[idx][j-num]\n``` \n\n3. None of 2 and 3 :\nIn this case we just simple do:\n```\ndp[idx][j-num] = dp[idx-1][j-num] + dp[idx-1][j-2*num] ...  + dp[idx-1][j - p*num]\n```\n\nNow instead of adding up from `k = 0` till `k = p` (`p` maybe same as `freq`), we can see if the current element falls among the first two categeries and just use the precalculated entries to speed up the process significantly.\nNow our transition will look like:\n```\nfor(int j = 0;j<=r;j++){\n    if(((freq+1)*num <= j)){\n        dp[idx][j] = \n        (dp[idx-1][j] + dp[idx][j-num] - \n            dp[idx-1][j-(freq+1)*num] + mod)%mod;\n    }\n    else if(num<=j){\n        dp[idx][j] =\n        (dp[idx-1][j] + dp[idx][j-num])%mod;\n    }\n    else{\n        for(int k=0;k<=freq and j>=k*num;k++){\n            dp[idx][j] = \n            (dp[idx][j] + dp[idx-1][j-k*num])%mod; \n        }\n    }\n}\n```\n\nThis does get accepted but we can further improve the space complexity as anytime we are updating the `idx` row of the table, we only need `idx-1` row of the table, so essentially we can just store two 1D vectors and keep updating them.\nYou can include zero too in the transition itself but I prefer to keep it simpler/faster and handle zero separately.\n\n# Complexity\n- Time complexity:\n$$O(rd)$$, where $d$ is number of distinct elements.\n\n- Space complexity:\n$$O(r)$$\n\n# Code\n```\n#define mod 1000000007\nclass Solution {\npublic:\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        unordered_map<int,int> count;\n        for(auto num:nums) count[num]++;\n        //handle zero separately\n        int zeroFreq = 0;\n        if(count.find(0)!=count.end()){\n            zeroFreq = count[0];\n            count.erase(0);\n            if(count.empty()) return zeroFreq + 1;\n        }\n        int n = count.size();\n        vector<long long> cur(r+1,0);\n        vector<long long> prev(r+1,0);\n\n        //base case\n        auto it = count.begin();\n        int base_num = it->first;\n        int base_freq = it->second;\n        for(int i=0;i<=r;i++){\n            if(i%base_num == 0 and i/base_num<=base_freq){\n                prev[i] = 1; \n//for zero it wouldn\'t have been simply 1, zero is the only number\n//that can give the sum of 0 in more than one ways, but it has been \n//dealt with already so base_num will surely not be zero.\n            }\n        }\n        it++;\n        while(it!=count.end()){\n            int num = it->first;\n            int freq = it->second;\n            for(int j = 0;j<=r;j++){\n                if(((freq+1)*num <= j)){\n                    cur[j] = \n                    (prev[j] + cur[j-num] - \n                     prev[j-(freq+1)*num] + mod)%mod;\n                }\n                else if(num<=j){\n                    cur[j] =\n                    (prev[j] + cur[j-num])%mod;\n                }\n                else{\n                    for(int k=0;k<=freq and j>=k*num;k++){\n                        cur[j] = \n                        (cur[j] + prev[j-k*num])%mod; \n                    }\n                }\n            }\n            it++;\n            prev = cur;\n            cur.assign(r+1,0);\n        }\n        long ans = 0;\n        for(int i = l;i<=r;i++){\n            ans = (ans + prev[i]) % mod;\n        }\n        return (ans*(zeroFreq + 1))%mod;\n    }\n}; \n\n\n```
['Dynamic Programming', 'C++']