K-Knapsack Problem || Detailed Explanation || Different Way to Think ||O(N*r)
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThis is a standard knapsack problem and a variation of 2585.\n\nIn general, knapsack 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThis is a standard knapsack problem and a variation of [2585](https://leetcode.com/problems/number-of-ways-to-earn-points/description/).\n\nIn general, knapsack DP problem is categorized into two sets: (1) 1-knapsack, with only 1 count per item; (2) infinite-knapsack, with infinitely many items. (1) requires us to iterate backwards in order not to double count while (2) requires us to iterate forwards in order to count all possibilities.\n\nFor k-knapsack question, with a specific count per item, there is also two ways starting from either (1) and (2) to think about it. (1) is the most intuitive and the most common way where you only need to add a few more items per iteration compared to 1-knapsack code. I learned(2) earlier and this approach doesn\'t seem very intuitive.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n`dp[i]` represents the number of ways to get a sum of `i`.\n\nWe get the count of each item first then iterate over the item and the count.\n\nIn each iteration, we first assume that we have infinitely many items and iterate forward. Now the meaning of `dp[i]` has slightly changed: we count the ways to `i` using infinitely many current item **plus** we also count the previous items for multiple times. So, next step is to remove the effect of multiple counts. Luckily, you can do this in one line and this should be done backwards.\n\nOther detail like count of 0 is omitted in the discussion.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N*r)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(r)\n\n# Code\n```\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n\n        MOD = 10**9+7\n\n        count = Counter(nums)\n\n        dp = [0 for i in range(r+1)]\n        dp[0] = 1\n\n        for key,val in count.items():\n            if key == 0:\n                continue\n            for i in range(key,r+1):\n                dp[i] = (dp[i] + dp[i-key]) % MOD\n            for i in range(r,(val+1)*key-1,-1):\n                dp[i] = (dp[i] - dp[i-(val+1)*key]) % MOD\n        \n        return sum(dp[l:r+1]) * (count[0]+1) % MOD\n                            \n```
['Python3']