Optimized Dynamic Programming
Intuition\nThis problem is similar to knapsack, so DP seems like a good approach.\n\n# Approach\nWe can try to approach this like a modified knapsack problem, w
# Intuition\nThis problem is similar to knapsack, so DP seems like a good approach.\n\n# Approach\nWe can try to approach this like a modified knapsack problem, where we take special care to account for duplicate elements. We can take care of duplicate elements by keeping a map from elements to their frequencies, then accounting for this while updating our cache.\n\nHowever, this will TLE.\n\nA key observation is to notice how the bounds state that $$\\mathrm{sum(nums)}\\le 2\\cdot 10^4$$. This means the number of distinct elements in $$\\mathrm{nums}$$ is limited. At best, we can have $1+2+\\dots+x\\le \\mathrm{sum(nums)}\\implies x\\le O(\\sqrt{\\mathrm{sum(nums)}})$ distinct elements. We can use this to our advantage.\n\nConsider adding or not adding some element `num`, and let `cache[i]` be the number of ways to obtain a sum of `i`. One downside of our DP is that it is slow to update `cache[i] = cache[i] + cache[i - num] + cache[i - 2 * num] + ... + cache[i - freq * num]`, especially if `freq` is large (i.e. when the number of distinct elements is small).\n\nHowever, we can speed this up by preprocessing with a prefix sum. This speeds up cases where the number of distinct elements is small, which is precisely what we want.\n\n# Complexity\n- Time complexity: $$O(r\\cdot \\min(n, \\sqrt{\\mathrm{sum(nums)}}))$$, where $$n=\\mathrm{len(nums)}$$\n\n- Space complexity: $$O(r + \\min(n, \\sqrt{\\mathrm{sum(nums)}}))$$\n\n# Code\n```java\nclass Solution {\n    static final int MOD = 1_000_000_007;\n\n    public int countSubMultisets(List<Integer> nums, int l, int r) {\n        TreeMap<Integer, Integer> numsMap = new TreeMap<>();\n        for (int num : nums) {\n            numsMap.put(num, numsMap.getOrDefault(num, 0) + 1);\n        }\n\n        long[] cache = new long[r + 1];\n        cache[0] = 1;\n\n        for (Map.Entry<Integer, Integer> entry : numsMap.entrySet()) {\n            int num = entry.getKey();\n            int freq = entry.getValue();\n\n            // preprocessing\n            long[] pSum = Arrays.copyOf(cache, r + 1);\n            for (int i = 0; i <= r; ++i) {\n                if (i >= num) {\n                    pSum[i] += pSum[i - num];\n                    pSum[i] %= MOD;\n                }\n            }\n\n            // update dp cache\n            for (int i = r; i >= 0; --i) {\n                if (num > 0) {\n                    int j = i - (freq + 1) * num;\n                    cache[i] = pSum[i] - (j >= 0 ? pSum[j] : 0);\n                    cache[i] = Math.floorMod(cache[i], MOD);\n                } else {\n                    cache[i] *= freq + 1;\n                    cache[i] %= MOD;\n                }\n            }\n        }\n\n        long res = 0;\n        for (int i = l; i <= r; ++i) {\n            res += cache[i];\n            res %= MOD;\n        }\n        return (int) res;\n    }\n}\n```
['Dynamic Programming', 'Java']