Bottom-Up DP & Sliding Window to avoid TLE
Intuition\n Describe your first thoughts on how to solve this problem. \nThe number of distinct elements (let it be m) the array can have is at most 200. It can
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe number of **distinct** elements (let it be `m`) the array can have is at most `200`. It can be verified by the sum of first `199` positive elements (`199*(199+1)/2=19900`, and then `0`). With this, we can develop a `O(sum*m)` solution.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet `dp[i]` be the number of ways we can make the sum `i`. We go through each distinct element and update our DP that way. Our goal is to traverse every sum once for each unique number.\n\nIn order to traverse every sum only once, we can treat every sum as `sum % current_number`, which means we try every modulo (which is `0 <= k < current_number`) and work with sums only with that modulo.\n\nFor example, if our number is `5`, and our modulo is `2`, we traverse `2,7,12,17,...`\n\nThe code doesn\'t actually use the modulo of the sum, but rather it starts from some offset from `sum`.\n\n**Since every offset covers an unique set of sums, trying every offset will cover all the sums!**\n\nIn order to update the DP, we take into account of the occurences of each number we try (`cnt[current_number]`). For example, if `current_number` is 5, and `cnt[5] = 4`, and we are updating the DP for sum `k`:\n`dp[k] += dp[k - 5] + dp[k - 10] + dp[k - 15] + dp[k - 20]`\n\nTo avoid TLE of going through occurences of the number and adding up all the DP values we can get, we use a sliding window. For the above example, when we move the window, if `dp[k - 5] + dp[k - 10] + dp[k - 15] + dp[k - 20]` is `cur`, we do `cur + dp[k - 25] - dp[k - 5]`\n\n**IMPORTANT: We must go from right to left, because that eliminates the possibility of using the updated dp values for the current number. We want to use the dp values from the previous number**\n\n\n# Complexity\n- Time complexity: $$O(sum(nums)*m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(sum(nums))$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution\n{\npublic:\n    int countSubMultisets(vector<int> &nums, int l, int r)\n    {\n        const int M = 1e9 + 7;\n        int ma = ranges::max(nums); // maximum element\n        int sum = accumulate(nums.begin(), nums.end(), 0);\n        nums.push_back(0); // clever handle case of nums having no 0\n        vector<int> cnt(ma + 1);\n        for (int v : nums)\n            cnt[v]++;\n        ranges::sort(nums);\n        nums.erase(unique(nums.begin(), nums.end()), nums.end());\n        vector<int> dp(sum + 1);\n        dp[0] = cnt[0];\n        for (int v : nums)\n        {\n            for (int j = 0; j < v; j++) // every modulo j\n            {\n                int cur = 0; // sum of all the appropriate DP values for the window\n                int p = sum - j; // points to left index of sliding window when the window is shifted\n                for (; p >= 0 && (sum - j - p) / v <= cnt[v]; p -= v)\n                    cur = (cur + dp[p]) % M;\n                for (int k = sum - j; k >= 0; k -= v)\n                {\n                    cur = (cur - dp[k] + M) % M; // take away, because dp[k] means we didn\'t use any occurence of the number\n                    dp[k] = (dp[k] + cur) % M;\n                    if (p >= 0)\n                    { // include the next DP in the sliding window\n                        cur = (cur + dp[p]) % M;\n                        p -= v;\n                    }\n                }\n            }\n        }\n        int ans = 0;\n        for (int i = l; i <= min(r, sum); i++)\n            ans = (ans + dp[i]) % M;\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Sliding Window', 'C++']