Go - Dynamic Programming Knapsack + Prefix Sum Solution
Intuition\nThe problem equals to slightly modified Knapsack. It can be solved using the Dynamic Programming approach, very similar to Coin Change problem(s).\n\
# Intuition\nThe problem equals to slightly modified *Knapsack*. It can be solved using the *Dynamic Programming* approach, very similar to *Coin Change* problem(s).\n```\nfunc countSubMultisets(nums []int, l int, r int) int {\n\tmultiset := make(map[int]int)\n\tfor _, num := range nums {\n\t\tmultiset[num]++\n\t}\n\tmem := make([]int, r+1)\n\tmem[0] = 1\n\tfor num, occ := range multiset {\n\t\tfor sum := r; sum >= 0; sum-- {\n\t\t\tvar ways int\n\t\t\tfor c := 0; c <= occ && sum-num*c >= 0; c++ {\n\t\t\t\tways = (ways + mem[sum-num*c]) % mod\n\t\t\t}\n\t\t\tmem[sum] = ways\n\t\t}\n\t}\n\tvar result int\n\tfor sum := l; sum <= r; sum++ {\n\t\tresult = (result + mem[sum]) % mod\n\t}\n\treturn result\n}\n\nvar mod int = 1e9 + 7\n```\nThe above solution yields pseudo-polynomial time complexity $$O(r \\cdot n)$$, where $$n$$ is the length of the input array. It results in TLE though for last test case(s).\nOne can improve the running time by relying on the problem constraint saying: $$sum(nums) \\le 2\\cdot 10^4$$. Since the nums consists of non-negative integers, we expect the limited number of unique elements, hence a lot of duplicates.\n\n# Approach\n1. Store all unique elements and their frequency in the *HashMap*.\n2. Initialize the cache $$mem$$, where $$mem[sum]$$ equals to the number of sub-multisets summing up to the $$sum$$.\n3. Base Case: $$mem[0]=1$$ (there is at least 1 sub-multisets summing up to 0, empty one).\n4. Iterate through all unique elements.\n4.1. Calculate the *Prefix Sum* based on the current cache state.\n4.2. Calculate the number of sub-multisets summing up to each $$sum \\in <0, r>$$ based on the *Prefix Sum*. Be careful with 0 element(s)!\n\n# Complexity\n- Time complexity:\n$$O(r\\cdot u)$$, where $$u$$ is the number of unique elements in the input array.\n\n- Space complexity:\n$$O(r+u)$$.\n\n# Code\n```\nfunc countSubMultisets(nums []int, l int, r int) int {\n\tmultiset := make(map[int]int)\n\tfor _, num := range nums {\n\t\tmultiset[num]++\n\t}\n\tmem := make([]int, r+1)\n\tmem[0] = 1\n\tprefix := make([]int, len(mem))\n\tfor num, occ := range multiset {\n\t\tcopy(prefix, mem)\n\t\tfor sum := num; sum <= r; sum++ {\n\t\t\tprefix[sum] = (prefix[sum] + prefix[sum-num]) % mod\n\t\t}\n\t\tfor sum := r; sum >= 0; sum-- {\n\t\t\tif num > 0 {\n\t\t\t\tmem[sum] = prefix[sum]\n\t\t\t\tif sum >= num*(occ+1) {\n\t\t\t\t\tmem[sum] = (mem[sum] - prefix[sum-num*(occ+1)] + mod) % mod\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tmem[sum] = (mem[sum] * (occ + 1)) % mod\n\t\t\t}\n\t\t}\n\t}\n\tvar result int\n\tfor sum := l; sum <= r; sum++ {\n\t\tresult = (result + mem[sum]) % mod\n\t}\n\treturn result\n}\n\nvar mod int = 1e9 + 7\n```
['Dynamic Programming', 'Prefix Sum', 'Go']