Take - NotTake DP
\n# Approach\n- We need to go for recursive solution with take and not-take each of the item from the nums array and keep evaluating sum and numbers of itmes we
\n# Approach\n- We need to go for recursive solution with take and not-take each of the item from the nums array and keep evaluating sum and numbers of itmes we have taken.\n- While doing so, check if the sum equals to the k, then we can have 2^(nums.size() - count) times subsequences that have sum equal k for a particular subsequence considered.\n- We need to memorise the answer to optimise runtime.\n\n\n# Code\n```\nclass Solution {\npublic:\n    int m = 1e9 + 7;\n    vector<vector<vector<int>>> dp;\n    \n    long long power(int n){\n        if(n <= 1) return (n+1);\n        long long res = power(n/2);\n        if(n%2) return (((res*res)%m)*2)%m;\n        return ((res*res)%m);\n    }\n    \n    long long solve(vector<int>& nums, int k, int i, int sum, int count){\n        if(sum == k) {\n            return power(nums.size() - count);\n        }\n        if(i >= nums.size() || sum > k ) return 0;\n        if(dp[i][count][sum] != -1) return dp[i][count][sum];\n        \n        long long take = solve(nums, k, i + 1, sum + nums[i], count + 1);\n        long long notTake = solve(nums, k, i + 1, sum, count);\n        return dp[i][count][sum] = (take + notTake)%m;\n    }\n    \n    int sumOfPower(vector<int>& nums, int k) {\n        dp.resize(100, vector<vector<int>>(110, vector<int>(110, -1)));\n        return solve(nums, k, 0, 0, 0);\n    }\n};\n```\n\n\n---\n\n<b> Here is an article of my last interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon:\nhttps://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted\n\n---
['C++']