C++ || Easy Dynamic Programming || O(k*(N^2)) || Take /not Take (Knapsack)
Intuition\n Describe your first thoughts on how to solve this problem. \nthe description is asking us how many subsequence can our right subsequence can be a pa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nthe description is asking us how many subsequence can our right subsequence can be a part of \n(1,2,3,4,5) \nlets say the required subsequence is (1,3,5) then this subsequence is part of (1,2,3,5) ,(1,3,4,5),(1,2,3,4,5),(1,3,5) \nso if (1,3,5) is the fullfilling our condition then our answer is 4 as  (1,3,5) is part of 4 subsequences(including itself)\n# Approach\n<!-- Describe your approach to solving the problem. -->\nfor a given subsequence answer is 2^(no. of elements not taken)\n\nso we track the number of elements taken in our subsequence and when the condition is fullfilled we calculate the answer using\nans= 2^(n-x)\nwhere n= no. of elements in the array \nx= no. of elements taken in the array\n\nHOW TO CHOOSE the subsequence ?\ntake/ no take (Knapsack dp), at each index either choose the current element and reduce the sum by nums[idx]\nor just skip this turn \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n*n*k)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n*n*k)\n# Code\n```\nclass Solution {\npublic:\n    using ll =long long;\n    ll mod=1e9 +7;\n    ll binPow(ll a, ll b){\n        if(b==0)\n            return 1;\n        ll ans= binPow(a,b/2);\n        ans=(ans*ans)%mod;\n        \n        if(b%2)\n            ans=(ans*a)%mod;\n        return ans;\n    }\n    \n    int solve(vector<int>& nums, int k,int idx,int taken, vector<vector<vector<int>>>&dp){\n        if(k<0)\n            return 0;\n        if(k==0)\n        {\n            ll n= nums.size();\n            ll ans=binPow(2,n-taken);\n            return ans;\n        }\n        if(idx==nums.size())\n            return 0;\n        if(dp[idx][k][taken]!=-1)\n            return dp[idx][k][taken];\n        \n        ll ans=0;\n        \n        ans+= solve(nums,k-nums[idx],idx+1,taken+1,dp);\n        ans+= solve(nums,k,idx+1,taken,dp);\n        return  dp[idx][k][taken]=ans%mod;\n        \n    }\n    int sumOfPower(vector<int>& nums, int k) {\n        vector<vector<vector<int>>>dp(nums.size(),vector<vector<int>>(k+1,vector<int>(nums.size()+1,-1)));\n        return solve(nums,k,0,0,dp);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']