Very Easy 0/1 KnapSack DP Pattern || Explained
Intuition\n\n- Apply 0/1 KnapSack to form target sum\n- once we have formed target, \n  say, we have used "taken" integers to make sum = target\n  then, for res
# Intuition\n```\n- Apply 0/1 KnapSack to form target sum\n- once we have formed target, \n  say, we have used "taken" integers to make sum = target\n  then, for rest "n-taken" elements, \n- we have 2 choices, either include them in sub-sequence or not\n  thus, 2^(n-taken) choices in total\n```\n\n# Complexity\n- Time complexity: $$O(n^2*k)$$ \n\n- Space complexity: $$O(n^2*k)$$ \n\n# Code\n```\n#define mod 1000000007\nclass Solution {\n    long long binpow(long long base, long long exp)\n    {   //function to calculate (base ^ exp)\n        long long ans = 1LL;\n        while(exp > 0)\n        {\n          if(exp & 1) {\n            ans = (ans * base) % mod;\n          }\n          base = (base * base) % mod;\n         exp >>= 1;\n        }\n     return ans;\n    }\n    long long solve(int i, int k, int taken, vector<int>& nums, int dp[101][101][101])\n    {   //if target sum is formed\n        if(k == 0) return binpow(2,nums.size()-taken); //return 2^(n-taken) choices\n        if(k < 0 || i == nums.size()) return 0; //invalid state\n       if(dp[i][taken][k] != -1) return dp[i][taken][k]; //memoization step\n\n       //apply simple take/notTake \n       long long take = solve(i+1,k-nums[i],taken+1,nums,dp) % mod;\n       long long notTake = solve(i+1,k,taken,nums,dp) % mod;\n       return dp[i][taken][k] = (take + notTake) % mod; //add both to get total ans\n    }\npublic:\n    int sumOfPower(vector<int>& nums, int k) {\n        int dp[101][101][101]; //basically, its (n*n*k) size dp\n        memset(dp,-1,sizeof(dp));\n        return solve(0,k,0,nums,dp);\n    }\n};\n```
['Dynamic Programming', 'C++']