DP + Combinatorics || logic explained
Explanation\n Describe your first thoughts on how to solve this problem. \nWe\'ll be using dp . But why ?\nAssume the question to be something like this , retur
# Explanation\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe\'ll be using dp . **But why ?**\nAssume the question to be something like this , return the no. of subsequences whose sum is \'k\' and length is \'l\'. As we can see we can use the subsequences of smaller length to form a subsequence of greater length , basically using the previous answers to calculate the new one. \n\n**state(k,l) = state(k-curElement, l-1)** -- no. of subsequences that can be formed including current element in the subsequence whose total sum is equal to (k-current element) and size one less.\n\nNow the interesting part of the question, *we don\'t have to calulate the no. of subsequences of the given array but for each subsequences of the array we have to calculate their subsequences count satisfying the sum constraint equat to \'k\'.*\n\nSo when we got any particular subsequence satisfying the sum constraint we only have to know in how many ways these subsequences can be a part of other subsequences.\n\nNow assume a case-\ngiven array length = n\nsubsequence length = l\n\n**In how many ways it can be a part of other subsequences ?**\n*out of **n** we have fixed **l** elements and remaining elements i.e **(n-l)** can either be present or absent so basically two choices for each **(n-l)** elements. \nSo when we have a particular subsequence of length \'**l**\' as a answer,the total subsequence that can be formed from that subsequence is **2^(n-l)**;*\n\nNow how to form a subsequence ?\nFor each element of the array we have two options --\n**1** - include in the subsequence , then we have two include it in our sum and our subsequence size will increase.\n**cal(v,currentIndex+1, totalLength, givenSum-v[i], curSubSeqLen+1)**\n\n**2** - we ignore the current element.\n**cal(v,currentIndex+1, totalLength, givenSum, curSubSeqLen);**\n\n*whenever we got a subsequence of sum \'**k**\' and some length **\'l\'** , we basically move to our base condition that we have got one subsequence, now have to consider all subsequences that can be formed from this i.e **2^(n-l)** where n is total length of the given array;*\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nFrom our dp states dp[n][k][n] , we can figure out that we have to calculate all the dp states . So T.C = **O(n.n.k)**\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nIt will be equal to our size of dp i.e **O(n.n.k)**\n\n# Code\n```\nclass Solution {\npublic:\n    int mod = 1000000007;\n\n//dp[n][k][n] -> first one for currentIndex,\n// second representing given sum, \n// third one for length of subsequence whose max value will be nothing but the given array size. \n\n    long long dp[105][105][105];\n    int cal(vector<int> &v,int i,int n,int k, int l){\n        if(i==n || k<0){\n            if(k==0){\n                return po(2,n-l);\n            };\n            return 0;\n        }\n        if(dp[i][k][l]!=-1){\n            return dp[i][k][l];\n        }\n        long long ans=cal(v,i+1,n, k-v[i],l+1);\n        ans%=mod;\n        ans+=cal(v,i+1,n,k,l);\n        return dp[i][k][l]=ans%mod;\n    }\n\n    long long po(long long a,long long b){\n        long long res=1;\n        while(b>0){\n            if(b&1){\n                res=(res*a);\n                res%=mod;\n            }\n            b=b>>1;\n            a=(a*a);\n            a%=mod;\n        }\n        return res;\n    }\n\n    int sumOfPower(vector<int>& nums, int k) {\n        int n=nums.size();\n        \n        memset(dp,-1,sizeof(dp));\n        long long res=cal(nums,0,n,k,0);\n       \n        return res;\n    }\n};\n```
['Dynamic Programming', 'Combinatorics', 'C++']