Easy to Understand + Important Concept Involved
Take a test case like [1,1,1,1,1,1], here we have 6 (1) . Now think properly of what we have to do :\n\n[1,1,1,1,1,1]-->[a,a,a,a,a] , [a,b,a,a], [a,b,b] etc;\n\
Take a test case like [1,1,1,1,1,1], here we have 6 (1) . Now think properly of what we have to do :\n\n[1,1,1,1,1,1]-->[a,a,a,a,a] , [a,b,a,a], [a,b,b] etc;\n\nIf we closely look its just like :\n\n6=1+1+1+1+1+1  => a+a+a+a+a+a\n6=1+2+1+1 =>a+b+a+a\n6=1+3+1=>a+c+a\n\n6=1+4 NOT VALID || We can only go upto 3 as given in ques (3presses);\n\nDoesn\'t this look similar to COIN-CHANGE Problem , But HERE IS A CATCH , here we have to compute all the PERMUTATIONS unlike COIN CHANGE where we calculated unique PERMUTATION.\n\nYou can take help from here regarding Permutation Thing : https://leetcode.com/problems/combination-sum-iv/discuss/1986766/did-u-missed-this-concept-permutations-vs-unique-permutations\n\nSolution is as Follows:\n\nclass Solution { \npublic:\n    \n    int COINCHANGE(int sum,int k){\n        int mod=1e9+7;\n        vector<int>coin={1,2,3};\n        if(k==7 || k==9){   //since we can press 4 times there\n            coin.push_back(4);\n        }\n        int n=coin.size();\n        vector<vector<int>>dp(n+1,vector<int>(sum+1,0));\n        \n        for(int i=0;i<=sum;i++){\n            dp[0][i]=0;\n        }\n        for(int i=0;i<=n;i++){\n            dp[i][0]=1;\n        }\n        \n        for(int k=1;k<=sum;k++){\n            for(int i=1;i<=n;i++){\n                if(k-coin[i-1]>=0){\n                    dp[i][k]=(dp[i-1][k]%mod+dp[n][k-coin[i-1]]%mod)%mod;\n                }\n                else{\n                    dp[i][k]=dp[i-1][k]%mod;\n                }\n            }\n        }\n        return dp[n][sum];\n    }\n    int countTexts(string s) {\n        \n        int cnt=0;\n        long long ans=1;\n        int mod=1e9+7;\n        s+=\'$\';\n        for(int i=1;i<s.size();i++){\n            if(s[i]==s[i-1]){\n                cnt++;\n            }\n            else{\n                int k=s[i-1]-\'0\';\n                ans=((ans%mod)*1LL*(COINCHANGE(cnt+1,k))%mod)%mod;  //Multiplication is done to have all the combinations\n                ans=ans%mod;\n                cnt=0;\n            }\n        }\n        return ans;\n        \n        \n    }\n };\n \n If it is still unclear, please let me know how can I help.
['Dynamic Programming', 'C']