C++ | 3-D DP - Memoization
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen we get a particular subsequence whose sum is equal to k then remaining values whic
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen we get a particular subsequence whose sum is equal to k then remaining values which are not present in these subsequences, we can either take or skip every value to make a subsequence. that count\'s to 2^(total length - len of current subsequence)\n\nThen we can simply apply Knapsack(pick, notPick) DP. We have 3 changing parameters(index, sum, count of taken values). so created 3-D DP.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^3)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^3)\n\n# Code\n```\n#define ll long long\n\nclass Solution {\npublic:\n    \n    ll power(int val, int po, int mod){\n        ll ans = 1;\n        \n        while(po--){\n            ans = (ans*val)%mod;\n        }\n        \n        return ans;\n    }\n    \n    ll helper(int i, int taken, int sum, int k, vector<int>& nums, int mod, vector<vector<vector<ll>>>& dp){\n        int n = nums.size();\n        \n        if(i>=n){\n            if(sum == k){\n                return power(2, n-taken, mod)%mod;\n            }\n            \n            return 0;\n        }\n        \n        if(dp[i][taken][sum] != -1) return dp[i][taken][sum];\n        \n        ll notTake = helper(i+1, taken, sum, k, nums, mod, dp)%mod;\n        ll take = 0;\n        if((sum+nums[i])<=k) take = helper(i+1, taken+1, sum+nums[i], k, nums, mod, dp)%mod;\n        \n        return dp[i][taken][sum] = (notTake+take)%mod;\n    }\n    \n    int sumOfPower(vector<int>& nums, int k) {\n        int mod = 1e9+7;\n        int n = nums.size();\n        vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(k+1, -1)));\n        return (int)helper(0, 0, 0, k, nums, mod, dp)%mod;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']