Python AC
Intuition\n Describe your first thoughts on how to solve this problem. \nWhat are the options for an element \'a\', it can be selected from [0, c[a]] times.\nSi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhat are the options for an element \'a\', it can be selected from [0, c[a]] times.\nSimple DP is giving TLE, others have mentioned a logic to turn internal linear time options logic to constant time.\nWrite down f(i, s) and f(i, s+a), get f(i, s+a) in terms of f(i, s), substitute s+a with s.\nf(i, s) = f(i+1, s) + f(i, s-nums[i]) + f(i+1, s-(c[nums[i]]+1)*nums[i]) \nConsider zero cases separately otherwise inf recursion cause of f(i, s-nums[i]). zeros can be added to any subset, you can add [0, c[0]] to all the subsets.\n\n# Code\n```\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        numsCount = {}\n        zeroCount = 0\n\n        for num in nums:\n            if num == 0:\n                zeroCount += 1\n            else:\n                if num not in numsCount:\n                    numsCount[num] = 1\n                else:\n                    numsCount[num] += 1\n        numsList = list(numsCount.keys())\n        dp = [[-1 for j in range(20001)] for i in range(len(numsList))]\n        m = 1000000007\n        \n        def countSubMultisetsRec(idx: int, s: int) -> int:\n            if s < 0:\n                return 0\n            if idx == len(numsList):\n                return 1\n            if dp[idx][s] != -1:\n                return dp[idx][s]\n            \n            ans = 0\n            nextIdx = idx + 1\n            maxCount = numsCount[numsList[idx]]\n            ans = (countSubMultisetsRec(nextIdx, s) + countSubMultisetsRec(idx, s - numsList[idx]) - countSubMultisetsRec(nextIdx, s - (maxCount + 1) * numsList[idx]) + m) % m\n            dp[idx][s] = ans\n            return ans\n        \n        ans = 0\n        ans = (countSubMultisetsRec(0, r) - countSubMultisetsRec(0, l - 1) + m) % m\n        return (ans * (zeroCount + 1)) % m\n```
['Python3']