Python Solution | 3-D DP | Memoization | Optimal
\n# Approach\n Describe your approach to solving the problem. \nWe need to go for a recursive solution with a \'take or leave\' approach for each of the item fr
\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe need to go for a recursive solution with a \'take or leave\' approach for each of the item from the `nums` array and keep evaluating sum and numbers of itmes we have taken. While doing so, check if the sum equals to `k`, then we can have `(2^(len(nums) - count)` times subsequences that have sum equal `k` for a particular subsequence considered. We need to memoize the answer to optimize runtime.\n\n# Code\n```python []\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        MOD = 1000000007\n        \n        @cache\n        def solve(idx: int, curSum: int, count: int) -> int:\n            if curSum == k:\n                return pow(2, len(nums) - count, MOD)\n            if idx >= len(nums) or curSum > k:\n                return 0\n            take = solve(idx + 1, curSum + nums[idx], count + 1)\n            leave = solve(idx + 1, curSum, count)\n            return (take + leave) % MOD\n\n        return solve(0, 0, 0)\n```
['Python3']