C++ recursive dp solution O(sqrt(r) * r)
We have at most 200 distinct elements so let\'s compress our array to array of pairs (a, c), where a - value, c - number of times it repeats in array\nLet\'s de
We have at most 200 distinct elements so let\'s compress our array to array of pairs (a, c), where a - value, c - number of times it repeats in array\nLet\'s define function get(i, s) - number of subsequences with sum less or equal than s starting from index i and tricky part of this problem is simplifying complexity of this function to constant, and it can be done using the equations below\n```\nget(i, s) = get(i + 1, s) + get(i + 1, s - a) + ... + get(i + 1, s - c * a)\nget(i, s + a) = get(i + 1, s + a) + get(i + 1, s) + ... + get(i + 1, s - (c - 1) * a) = get(i, s) + get(i + 1, s + a) - get(i + 1, s - c * a)\nlet x = s + a => get(i, x) = get(i, x - a) + get(i + 1, x) - get(i + 1, x - (c + 1) * a)\n```\nso now solution for the problem is straight-forward\n```\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        using ll = long long;\n        constexpr int MOD = 1\'000\'000\'007;\n        unordered_map<int, int> m;\n        for (const auto v: nums) {\n            ++m[v];\n        }\n        vector<pair<int, int>> v;\n        const ll zeroesCount = m[0];\n        m.erase(0);\n        for (const auto& p : m) {\n            v.push_back(p);\n        } \n        const int n = size(v);\n        vector<vector<int>> dp(n, vector<int>(r + 1, -1));\n        function<ll(int, int)> getOrCompute;\n        getOrCompute = [&](int i, int sum) -> ll {\n            if (sum < 0) {\n                return 0;\n            }\n            if (i == n) {\n                return 1;\n            }\n            if (dp[i][sum] != -1) {\n                return dp[i][sum];\n            }\n            const auto[x, c] = v[i];\n            return dp[i][sum] = (getOrCompute(i + 1, sum) + getOrCompute(i, sum - x) - getOrCompute(i + 1, sum - (c + 1) * x) + MOD) % MOD;\n        };\n        return (getOrCompute(0, r) - getOrCompute(0, l - 1) + MOD) * (zeroesCount + 1) % MOD;\n    }\n```\nAdditional note: we have to treat zeroes separately because \n```\nget(i, x) = get(i, x - a) + ...\n```\nwill lead to endless recursion
['C++']