EASY DP! 3D -> 2D and explaining WHY we use sliding window
Intuition\nClearly, there can only be $\sqrt{r}$ distinct numbers. The way to see this is to notice the smallest possible sum of $n$ distinct numbers is\n\large
# Intuition\nClearly, there can only be $\\sqrt{r}$ distinct numbers. The way to see this is to notice the smallest possible sum of $n$ distinct numbers is\n$$\\large 1+2+3+\\dotsc+m = \\frac{m(m+1)}{2}$$, therefore if $\\frac{m(m+1)}{2} \\leqslant r$ then $m \\leqslant O(\\sqrt{r})$\n\nWith this in mind, let\'s represent the array as distinct numbers coupled with their frequencies.\n\nExample:\n$[1,2,2,3] \\to [1_1,2_2,3_1]$\n\nAnyway, a naive DP idea is \n$\\large \\text{dp}[i][L][R]$ represents the number of multisums between $L$ and $R$ considering only $[i:]$ onwards. (from index $i$ to the end)\n\nThe transitions for this are:\n\n$\\large \\text{dp}[i][L][R] = \\sum\\limits_{h=0}^{\\text{freq}[a_i]} \\text{dp}[i+1][\\text{max}(0,L-h \\cdot a_i)][R-h \\cdot a_i]$\nwhere $h$ basically counts how MUCH of element $i$ we take.\n\nand if $R-h \\cdot a_i < 0$ then return $0$ as it\'s not possible to make a sum fit within $L \\leqslant S \\leqslant R$ (we\'re only dealing with positive numbers here!)\n\nAnyway, this is horribly slow. At least it\'s polynomial time. The TC of this is $O(n \\cdot r^2)$, despite the loop, because it runs once for every element in the original array (including dupes).\n\n\n## Optimization #1\n\nWe don\'t need to track both $L$ and $R$. Just one. Let\'s track $R$ and say $\\text{dp}[i][R]$ epresents the number of multisums $\\leqslant R$ considering only $[i:]$ onwards. (from index $i$ to the end)\n\nThen, our answer is $\\text{dp}[0][R] - \\text{dp}[0][L-1]$\n\n$\\Large \\text{dp}[i][R] = \\sum\\limits_{h=0}^{\\text{freq}[a_i]} \\text{dp}[i+1][R-h \\cdot a_i]$\n\nNow we are in business. However, evaluating this is $O(nr)$. It ain\'t gonna pass. We need $O(mr)$. That sum is the annoying part. There\'s guaranteed to be dupes, so we need to make use of that.\n\n## Optimization #2\n\nOkay this one is weird, I\'ll show then explain.\n\nSuppose we are at index $3$ with current sum $9$, and $a[3] = 3$, $\\text{freq}[a_3] = 2$\nThen our sum looks like \n\n$\\Large \\color{white} \\text{dp}[3][9] = \\sum\\limits_{h=0}^{2} \\text{dp}[4][9-h \\cdot 3] = \\boxed{\\text{dp}[4][9] + \\text{dp}[4][6] + \\text{dp}[4][3]}$\n\nOkay, nothing special here. NOW! Let\'s look at the EXACT same scenario but this time $R = 12$. Just watch what happens.\n$\\large \\text{dp}[3][12] = \\sum\\limits_{h=0}^{2} \\text{dp}[4][12-h \\cdot 3] = \\text{dp}[4][12] + \\text{dp}[4][9] + \\text{dp}[4][6]$\n\nThis is exactly the same as \n$\\large \\color{white} \\text{dp}[4][12] + \\text{dp}[4][9] + \\text{dp}[4][6] = \\color{red} \\text{dp}[4][12] \\color{white} + \\boxed{\\text{dp}[4][9] + \\text{dp}[4][6] + \\text{dp}[4][3]} \\color{red} - \\text{dp}[4][3]$\n\nIn other words,\n$\\Large \\color{white} \\text{dp}[3][12] = \\color{red} \\text{dp}[4][12] \\color{white} + \\text{dp}[3][9] \\color{red} - \\text{dp}[4][3]$\n\nOur sum is gone. Just like that. Now, to encapsulate what we have learned, we can write it in this equation.\n\n$\\large \\color{white} \\text{dp}[i][R] = \\color{red} \\text{dp}[i+1][R]  \\color{white} + \\text{dp}[i][R-a_i] \\color{red} - \\text{dp}[i+1][R-(\\text{freq}[a_i] + 1)a_i)]$\n\nNice!\n\nOur base case is quite simple, $\\large \\text{dp}[n][x] = 1$ for $x \\leqslant r$\nYou can think of it as a reward for reaching the finish line while being less than $r$.\n\n## Complication\n\nIf you have 0\'s. It breaks (LOL). It shouldn\'t be too hard to see why, the DP golden equation we derived just breaks. So the way to deal with it is to realise what the presence of a 0 really means. Let\'s say the answer to the question WITHOUT any 0\'s is $x$. Then, adding one zero will double that answer. Why? Because we can add a 0 to each of those subsets that works, and we can leave it alone. So we get the original PLUS the original with a 0 appended to it. \n\nIf we have two 0\'s, you might think it\'s quadruple. But, we can\'t have the **same** multiset (i.e. you can only append nothing, one zero, or both zeroes.). So really it\'s just the same situation but we add $x$ again. \n\nBasically, it\'s $\\huge (1+\\text{number of 0\'s}) \\cdot \\text{ans}$ \n\n\n# Complexity\n- Time complexity: $$\\large \\color{pink} O\\left(r \\cdot \\text{min}(n,\\sqrt{r})\\right)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$\\large \\color{pink} O\\left(r \\cdot \\text{min}(n,\\sqrt{r})\\right)$$\n\n# Code\n\nIgnore the Mint stuff, that\'s just to make the actual CODE cleaner (no need to fill the screen with nasty % MOD\'s).\n```\ntypedef long long ll;\ntypedef unsigned long long ull;\ntypedef vector<int> vi;\nconst int MOD = (int) 1e9 + 7;\n\ntemplate<ll mod = MOD>\nstruct mint {\n    ll x;\n\n    mint() : x(0) {}\n\n    mint(ll _x) {\n        _x %= mod;\n        if (_x < 0) _x += mod;\n        x = _x;\n    }\n\n    mint &operator+=(const mint &a) {\n        x += a.x;\n        if (x >= mod) x -= mod;\n        return *this;\n    }\n\n    mint &operator-=(const mint &a) {\n        x += mod - a.x;\n        if (x >= mod) x -= mod;\n        return *this;\n    }\n\n    mint &operator*=(const mint &a) {\n        x = (ull) x * a.x % mod;\n        return *this;\n    }\n\n    mint pow(ll pw) const {\n        mint res = 1;\n        mint cur = *this;\n        while (pw) {\n            if (pw & 1) res *= cur;\n            cur *= cur;\n            pw >>= 1;\n        }\n        return res;\n    }\n\n    mint inv() const {\n        assert(x != 0);\n        ll t = x;\n        ll res = 1;\n        while (t != 1) {\n            ll z = mod / t;\n            res = (ull) res * (mod - z) % mod;\n            t = mod - t * z;\n        }\n        return res;\n    }\n\n    mint &operator/=(const mint &a) {\n        return *this *= a.inv();\n    }\n\n    mint operator+(const mint &a) const {\n        return mint(*this) += a;\n    }\n\n    mint operator-(const mint &a) const {\n        return mint(*this) -= a;\n    }\n\n    mint operator*(const mint &a) const {\n        return mint(*this) *= a;\n    }\n\n    mint operator/(const mint &a) const {\n        return mint(*this) /= a;\n    }\n\n    bool operator==(const mint &a) const {\n        return x == a.x;\n    }\n\n    bool operator!=(const mint &a) const {\n        return x != a.x;\n    }\n\n    bool operator<(const mint &a) const {\n        return x < a.x;\n    }\n\n    friend ostream &operator<<(ostream &out, const mint &m) {\n        out << m.x;\n        return out;\n    }\n};\n\nusing Mint = mint<MOD>;\n\n\nclass Solution {\npublic:\n\n    Mint dp[201][(int) 2e4 + 3];\n    int freq[(int) 2e4 + 3];\n    int countSubMultisets(vector<int>& a, int l, int r) {\n    vi b;\n    for (auto x: a) {\n        if (freq[x] == 0 && x != 0)\n            b.emplace_back(x);\n        freq[x]++;\n\n    }\n\n    int n = b.size();\n    for (int j = 0; j <= r; ++j) \n        dp[n][j] = 1;\n    \n\n    for (int i = n-1; i >= 0; --i){\n        for (int j = 0; j <= r; ++j){\n            dp[i][j] = dp[i+1][j];\n            if (j-b[i] >= 0) {\n                dp[i][j] += dp[i][j - b[i]];\n                if (j-(freq[b[i]]+1)*b[i] >= 0)\n                    dp[i][j] -= dp[i+1][j-(freq[b[i]]+1)*b[i]];\n            }\n        }\n    }\n\n\n    return ((dp[0][r] - (l-1 >= 0 ? dp[0][l-1] : 0))*(1+freq[0])).x;\n    }\n};\n```
['Math', 'Dynamic Programming', 'Sliding Window', 'C++']