Thought process explained for interview. (C++)
Observations:\n- Order of number matter here, because 1,2,1 is same as 1,1,2. So we don\'t want duplicates.\n- For a particular number num, we can either take 1
Observations:\n- Order of number matter here, because 1,2,1 is same as 1,1,2. So we don\'t want duplicates.\n- For a particular number num, we can either take 1 times, 2 times... frequency[num] times.\n- What if the required problem was to get ans for a particular sum.\n- It would be coin change problem, where order matters.\n- Let dp[i] = Answer for sum i\n- Since order of number matter here, the transition would be, we want to calculate all possible sum that we can make from a particular number *num* (including multple times). So for that we would need the frequencey of that number too.\n- The transition would be like this\n```\nfor(auto &c : coins){\n    int num = c.first;\n    int freq = c.second;\n    //Calculate all possibile sum that we could make from a particular number num\n\n    //Iterate over the sum\n    for(int sum = r;sum>=0;sum--){\n\n        //Iterate over all the numbers that we can make from num.\n        for(int f = 1;f<=k;f++){\n            if(sum - f*num>=0)\n            dp[sum]+=dp[sum - f*num];\n        }\n    }\n}\n```\nWhy are traversing from r to 0 and not from 0 to r?\nNo one would tell you that! But the intuition behind is that, we have limited supply of each number. So we want to calculate all the sum that we have made without the use of the number num. When we are calculating from 0 to r, what happens let me explain with an example.\n\nLets suppose num = 3 with a frequencey of 1\nAnd we update dp[6] += dp[6-3]\nif dp[3] = 2, then dp[6] would be 2 (assumption) and we have used the number 3 here.\n\nNow when we calculate dp[9], we would do dp[9-3] which is dp[6]. But in dp[6] contains the answer to make 6 including the number 3(our num). But we have already used that number 3 in making 6. So, how are we calculating to do that for 9?\n\nBut we we first calculate for 9\ndp[9] += dp[6]. Now dp[6] contains the answer without using 3.\nThen we calculate dp[6].\nand so on.\nGot the point?\n\n***Now,what is the time complexity of this?\nO(c*r*f)***\nc can be upto 200 because sum of n is 40000. If we take each element unique,then we have 1 + 2 + 3 ... last = 40000. last(last+1)/2 = 40000.\nLast is approxamitely 200.\n\nBut f could be large. So we need to reduce f right?\n\n### How are we doing to do that?\n\nI initially got confused about this. Here is a beautiful implementation of prefix sum.\nSee in this loop what we are doning?\n```\n for(int sum = r;sum>=0;sum--){\n\n        //Iterate over all the numbers that we can make from num.\n        for(int f = 1;f<=k;f++){\n            if(sum - f*num>=0)\n            dp[sum]+=dp[sum - f*num];\n        }\n    }\n```\n\nIf we write for each sum \ndp[sum] = dp[sum - num] + dp[sum - 2*num] + dp[sum - 3*num]....\nLets see example, assume num = 3\nThen what would be dp[10]? It will be dp[7] + dp[4] + dp[1]...\nWhat would be dp[15]? It would be dp[12] + dp[9] + dp[6]..\nSee the intervals? 1 4 7 10 13...\nNext is 2 5 8 11 14 17\nNext is 3 6 9 12 15....\n\nLets create the prefix for interval 3 6 9 12 15\nNow lets assume the frequency of element 3 is 2\nWhat would be my ans?\ndp[15] = dp[12] + dp[9]\nCan we say that it is prefix[12] - prefix[6]?\nOr prefix[15] - prefix[15 - (3 * 3)]\n\n*Or prefix[sum] - prefix[sum - (freq + 1) * num];*\n\nNext how do we create the prefix array?\nSimple\n```\nprefix = dp;\nfor(int i = 0;i<=r;i++){\n    prefix[i]+=prefix[i-num];\n}\n```\n\nNow our code becomes\n```\n        for(auto &i : m){\n            if(i.first==0){\n                dp[0]+=i.second;\n                continue;\n            }\n            long long ele = i.first,c = i.second;\n            vector<long long>prefix = dp;\n            for(int i = 0;i<=r;i++){\n                if(i-ele>=0){\n                    prefix[i]+=prefix[i-ele];\n                }\n            }\n            for(int j = r;j>=1;j--){\n                int k = j - ele * (c+1);\n                if(k<0) dp[j] = prefix[j];\n                else dp[j] = prefix[j] - prefix[k];\n            }\n\n        }\n\n```\nJust add the mod.\n\nOur final answer becomes dp[l] + dp[l+1]..dp[r].\nWe successfully removed the f factor from the code. \n\n\n# Code\n```\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    //For all the sum\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        map<int,int>m;\n        for(auto &i : nums) m[i]++;\n        vector<long long>dp(r+1,0);\n        dp[0] = 1;\n        for(auto &i : m){\n            if(i.first==0){\n                dp[0]+=i.second%mod;\n                continue;\n            }\n            long long ele = i.first,c = i.second;\n            vector<long long>prefix = dp;\n            for(int i = 0;i<=r;i++){\n                if(i-ele>=0){\n                    prefix[i]+=prefix[i-ele]%mod;\n                    prefix[i]%=mod;\n                }\n            }\n            for(int j = r;j>=1;j--){\n                int k = j - ele * (c+1);\n                if(k<0) dp[j] = prefix[j];\n                else dp[j] = prefix[j] - prefix[k];\n                dp[j]+=mod;\n                dp[j]%=mod;\n            }\n\n        }\n        long int ans = 0;\n        for(int i = l;i<=r;i++){\n            ans+=dp[i];\n            ans%=mod;\n        }\n        return ans;\n    }\n   \n};\n```
['C++']