Easy DP Solution
Approach\n Describe your approach to solving the problem. \nCount occurrences of each distinct number in countArr.\n\ndp[i][sum] = dp[i+1][sum + k * countArr[i]
# Approach\n<!-- Describe your approach to solving the problem. -->\nCount occurrences of each distinct number in `countArr`.\n\n`dp[i][sum] = dp[i+1][sum + k * countArr[i].number]`, where k is in range `[0, countArr[i].count]`.\n\nIf `sum > r` we can early stop since all number are non-negative.\nIf `i == countArr.length` return `1` if `sum` in range `[l, r]` or `0` otherwise.\n\n\n# Complexity\n- Time complexity: $$O(n * r)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n * r)$$ but can reduced to $$O(r)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    static final int MOD = 1_000_000_007;\n    int l, r, n;\n    int calc(Integer[][] dp, int[][] countArr, int idx, int sum) {\n        if (sum > r) {\n            return 0;\n        }\n        if (idx == n) {\n            if (sum >= l && sum <= r) {\n                return 1;   \n            }\n            return 0;\n        }\n        if (dp[idx][sum] != null) {\n            return dp[idx][sum];\n        }\n        int res = 0;\n        int currNum = countArr[idx][0];\n        int currCount = countArr[idx][1];\n        int currSum = sum;\n        for (int i = 0; i <= currCount; i++) {\n            res = (res + calc(dp, countArr, idx + 1, currSum)) % MOD;\n            currSum += currNum;\n        }\n        dp[idx][sum] = res;\n        return res;\n    }\n    public int countSubMultisets(List<Integer> nums, int l, int r) {\n        this.l = l;\n        this.r = r;\n        Map<Integer, Integer> count = new HashMap<>();\n        for (int num : nums) {\n            if (num <= r) {\n                count.put(num, count.getOrDefault(num, 0) + 1);\n            }\n        }\n        n = count.size();\n        int i = 0;\n        int[][] countArr = new int[n][2];\n        for (Map.Entry<Integer, Integer> e : count.entrySet()) {\n            countArr[i][0] = e.getKey();\n            countArr[i][1] = e.getValue();\n            i++;\n        }\n        Integer[][] dp = new Integer[n + 1][r + 1];\n        return calc(dp, countArr, 0, 0);\n    }\n}\n```
['Java']