Super Short 2D DP Solution with Explanation | C++ | Take or Not Take | Space Optimization
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nLet\'s imagine we are i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet\'s imagine we are index \'i\' with current sum \'s\' ...\nNow,\n1) If we include current value in sum (only if curr value <= sum) :\nOur answer will be simply be equal to answer of next state which is,\ndp[i+1][s-nums[i]]. This is because now the current index is for sure to be included in subsequence.\n\n2) If we exclude current value in sum :\nNow our answer will be twice the answer of next state which is 2*(dp[i+1][s]). Why is it so? This is because , in this case the current value is not contributing to the sum . So if we are able to generate sum from further part and we are getting such \'p\' subsequences then our answer will be 2*p where p are the subsequences with current index included and p are those where current index is excluded. Remember this index if included or excluded isn\'t really contributing to the sum this is just contributing to the length of subsequence.\n\nNow final answer for state [i][s] :\ndp[i][s] = 2*(dp[i+1][s]) + dp[i+1][s-nums[i]].\n\nCan we optimize the solution even more? \nYes, as we can see that the state \'i\' is only dependent on state \'i+1\' so we can reduce the space complexity from O(n*k) to O(k). You can do it yourself !\n\nThat\'s it from my side !\n\nIf it helped you in anyway please do upvote and if you want ,you can follow me on LinkedIn where I post more of my experiences and DSA journey !\n\n**My LinkedIn :**\n[https://www.linkedin.com/in/vedant-rawale-9992a924b/]()\n\n# Complexity\n- Time complexity: **O(n*k)**\n \n\n- Space complexity: **O(n*k)**\n\n  **Can be reduced to O(k) as I said !**\n\n# Code\n```\n#define ll long long\n\nclass Solution {\npublic:\n    \n    const int mod = 1000000007;\n    \n    int sumOfPower(vector<int>& nums, int k) {\n        int n = nums.size();\n        vector<vector<ll> > dp(n+1,vector<ll> (k+1,0));\n        dp[n][0] = 1;\n        for(int i =n-1;i>=0;i-- ){\n            for(int s = 0;s<=k;s++){\n                ll currnottake = (((dp[i+1][s])%mod)*2)%mod;\n                ll currtake = 0;\n                if(s>=nums[i]) currtake = dp[i+1][s-nums[i]]%mod;\n                dp[i][s] = (currnottake%mod + currtake%mod)%mod;  \n            }\n        }\n        return dp[0][k];\n        \n        \n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']