3-D experience
Approach\nI want to know the contribution of any set of numbers in the final answer. \nFor example in the test case [2,3,1,4,5]. First we will find all the sets
# Approach\nI want to know the contribution of any set of numbers in the final answer. \nFor example in the test case [2,3,1,4,5]. First we will find all the sets of numbers whose sum is equal to k=6. There are two sets of numbers one with indexes 0,3 and other with indexes 2,4.\nLet us take one of the set 0,3. Elements are 2 and 4. We can see their sum is equal to 6.\nWe need to know, how many subsequences these two elements will be present in.\nThe subsequences are -\n[2,4],[2,3,4],[2,1,4],[2,4,5],[2,3,1,4],[2,3,4,5],[2,1,4,5],[2,3,1,4,5].\nBut how are we going to calculate them?\nThe answer is that we will definately have these two elements in all our subsequeces and for rest of us we do have a choice whether to take or not. So, we will have 2^(total elements-elements which will definately come=elements for which we have a choice), this is basically multiply 2(take and not take) the number of times we have a choice.\nSimilarly, we can find contribution of every such set and add in our final answer.\nIF YA SMELL WHAT WE ARE COOKING NOW, lets finish the story with the code. \n\n\n\n# Code\n```\nclass Solution {\npublic:\n    const long long M=1e9+7;\n    long long dp[101][101][101];\n\n    long long cal(int x){\n        long long res=1;\n\n        while(x--){\n            res=((res%M)*2)%M;\n        }\n\n        return res%M;\n    }\n\n    long long func(vector<int> &nums,int ind,int cur_sum,int len,int &tar,int &n){\n        // will consider a set of numbers only if thier sum is \n        // equal to the target\n        if(ind==n&&cur_sum==tar) return cal(n-len)%M;\n        else if(ind==n) return 0;\n\n        if(dp[ind][cur_sum][len]!=-1) return dp[ind][cur_sum][len];\n\n        long long choose=0,notChoose=0;\n\n        if(cur_sum+nums[ind]<=tar) choose=func(nums,ind+1,cur_sum+nums[ind],len+1,tar,n)%M;\n        notChoose=func(nums,ind+1,cur_sum,len,tar,n)%M;\n\n        return dp[ind][cur_sum][len]=(choose%M+notChoose%M)%M;\n    }\n\n    int sumOfPower(vector<int>& nums, int k) {\n        int n=nums.size();\n        memset(dp,-1,sizeof(dp));\n\n        return (int)func(nums,0,0,0,k,n);\n    }\n};\n```
['Dynamic Programming', 'C++']