C++ | 3D dp solution | Simplest HARD labelled problem
Intuition\n Describe your first thoughts on how to solve this problem. \nWe donot want to check through all the subsequences of the subsequence \nas it will tak
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe donot want to check through all the *subsequences of the subsequence* \nas it will take a lot of time and increase complexity.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe try to think of the subsequences that add up to `K` and  make combination with the remaining elements from the array which were not taken in the chosen subsequence.\nConsidering the first example `[1,2,3]` \nSay we take the subsequence `[1,2]`  that add up to `k=3` \nso the other subsequence that can be made from the array keeping {1,2} will be `[1,2] and [1,2,3]` that means `2` subsequences\nsimilarly the other subsequence that can be made is `[3]` (choosing only 3)\nso all the subsequences that can be made with [3] in it are\n`[1,2,3] ,[1,3],[2,3],[3]` that means we get `4` subsequences or we can say `2^2` or `2^(number of elements not included )`\nSo for every subsequence that we get thta sum to K\nwe add this to our answer.\nBut we also need to keep a modular power function to handle overflows.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n* n *k)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n * n* k) for the dp array\n# Code\n```\nint mod=1e9+7;\n#define ll long long\nclass Solution {\npublic:\n    //modular power function to avoid overflows\n    int power(ll x, ll y, int mod)\n    {\n\n        // Initialize answer\n        ll res = 1;\n\n        // Check till the number becomes zero\n        while (y > 0) {\n\n            // If y is odd, multiply x with result\n            if (y % 2 == 1)\n                res = (res * x)%mod;\n\n            // y = y/2\n            y = y >> 1;\n\n            // Change x to x^2\n            x = (x * x)%mod;\n        }\n        return res % mod;\n    }\n    //i->index \n    //sum->current sum of taken elements \n    //taken->no. of taken elements\n    ll solve(int i,int sum,int taken,vector<int>&nums,int k,int n,vector<vector<vector<int>>>& dp)\n    {\n        if(i==n)\n        {\n            if(sum==k)return power(2,n-taken,mod);\n            else return 0;\n        }\n        if(dp[i][sum][taken]!=-1)return dp[i][sum][taken];\n\n        ll ans=0;\n        //take only if sum does not exceed k\n        if(sum+nums[i]<=k)\n        {\n            ans+=solve(i+1,sum+nums[i],taken+1,nums,k,n,dp)%mod;\n        }\n        //not take\n        ans+=solve(i+1,sum,taken,nums,k,n,dp)%mod;\n        \n        return dp[i][sum][taken]=ans%mod;\n    }\n    int sumOfPower(vector<int>& nums, int k) {\n        int n=nums.size();\n        vector<vector<vector<int>>>dp(n,vector<vector<int>>(k+1,vector<int>(n+1,-1)));\n        return solve(0,0,0,nums,k,n,dp);\n    }\n};\n```
['C++']