JS Solution - Knapsack - It somehow got accepted LOL
I solved it as a variant of snapsack, which may not be efficient, but it somehow got accepted.\nAt first, I used Maps for sumsMapPre and sumsMapCur, and it hit 
I solved it as a variant of **snapsack**, which may not be efficient, but it somehow got accepted.\nAt first, I used **Maps** for `sumsMapPre` and `sumsMapCur`, and it hit me with a TLE. So I switch to arrays, I\'m a little surprised that this small optimization can beat the judge.\n\n# Complexity\n- let `n = nums.length`\n- Time complexity: $$O(nr)$$\n- Space complexity: $$O(r)$$\n\n# Code\n```js\nlet MOD = 1000000007;\nlet sumsMapPre = Array(20001).fill(0);\nlet sumsMapCur = Array(20001).fill(0);\nlet sumsArr = Array(20001).fill(0);\n\n/**\n * @param {number[]} nums\n * @param {number} l\n * @param {number} r\n * @return {number}\n */\nvar countSubMultisets = function (nums, l, r) {\n  let n = nums.length;\n  nums.sort();\n  sumsMapCur.fill(0);\n  sumsMapPre.fill(0);\n  sumsMapCur[0] = 1;\n  let t = 0;\n  let tt = 0;\n\n  let acc = 0;\n  for (let i = 0; i < n; i++) {\n    if (nums[i] == nums[i - 1]) acc += nums[i];\n    else {\n      tt = t;\n      acc = nums[i];\n\n      for (let j = t; j >= 0; j--) {\n        sumsMapPre[sumsArr[j]] =\n          (sumsMapCur[sumsArr[j]] + sumsMapPre[sumsArr[j]]) % MOD;\n        sumsMapCur[sumsArr[j]] = 0;\n      }\n    }\n\n    for (let j = tt; j >= 0; j--) {\n      let newSum = sumsArr[j] + acc;\n      if (newSum <= r) {\n        if (!sumsMapCur[newSum] && !sumsMapPre[newSum]) {\n          sumsArr[++t] = newSum;\n        }\n\n        let cnt = (sumsMapPre[sumsArr[j]] + sumsMapCur[newSum]) % MOD;\n        sumsMapCur[newSum] = cnt;\n      }\n    }\n  }\n\n  let res = 0;\n  for (let i = l; i <= r; i++)\n    res = (res + sumsMapPre[i] + sumsMapCur[i] ?? 0) % MOD;\n\n  return res;\n};\n```
['Dynamic Programming', 'JavaScript']