Subset of subset DP (a new way of thinking)
Intuition\nthis question is basically similar to knapsack having target ==k i.e we have to find number of subsequences having target equalt to k .\n\n# Approach
# Intuition\nthis question is basically similar to knapsack having target ==k i.e we have to find number of subsequences having target equalt to k .\n\n# Approach\nfirst we see in question that we have to generate all subsequences and in all subsequencce take a first subsequence and we have to find number of subsequences in which target==k but this approach is quite tidious also difficult to code .\n \n2nd one--->  this is standard problem(subset of subset dp)\nthink in that way like of subset of subset problem ,it,s not the outof box idea but think gives a new perspective to think \n-------------------------- original sequence array\n _ _ _  _ _  _ here we take a sequence either pick or not pick\n-_ _ _ _ _ subsequence we put\nabove element is not pick then we sum not changes ist time\nif element is pice in 2nd sequence but we don\'t pick in third subset of subset this is example of not pick element. so we multiply by 2 in notpick case \nand as usual in pick case \nthis is the main idea keep it remember for a long time\n\n# Complexity\n- Time complexity:\n0(n*k) \n\n- Space complexity:\n\n\n# Code\n```\nclass Solution {\npublic:\nint mod=1e9+7;\nint rec(int i,vector<int>&nums,int k,int sum,vector<vector<int>>&dp)\n{   // base case\n    if(sum>k) return 0;\n    if(i==nums.size()) return sum==k;\n    if(dp[i][sum]!=-1) return dp[i][sum];\n// basis knapsack varitaion\n    int take=0;\n    if(nums[i]<=k){\n     take=rec(i+1,nums,k,sum+nums[i],dp)%mod; }\n    int notTake=((rec(i+1,nums,k,sum,dp))*2)%mod;\n     return dp[i][sum]= (take+notTake)%mod;\n    \n}\n\n    int sumOfPower(vector<int>& nums, int k) {\n        int n=nums.size();\n        vector<vector<int>> dp(n,vector<int>(k+1,-1));\n       return rec(0,nums,k,0,dp);\n   \n    }\n};\n```
['Dynamic Programming', 'C++']