DP python
Intuition\nDynamic Programming (DP)\n\n# Approach\nGet the sum of power of all subsequences of nums is just an extra step for the main problem, finding the numb
# Intuition\nDynamic Programming (DP)\n\n# Approach\nGet the sum of power of all subsequences of nums is just an extra step for the main problem, ```finding the number of subsequences with a sum equal to k ``` but that extra step implies solve this problem in an specific way. Specifically, we need to determine the number of sequences of length `l` with a sum equal to `k`.\n\nWe need to solve for each length because, at the end, we require the count for all subsequences. It\'s easy to see that if a subsequence $s$ has a sum equal to $k$, that specific subsequence can be part of other subsequences of the total array. More specifically, a subsequence of length $l$ is also a subsequence of $2^{n-l}$ other subsequences. Thus, if we obtain an array that specifies, for each possible length, the number of subsequences of that length with a sum equal to $k$, then the answer will be given by:\n\n$$\n\\sum_{i=1}^{n} dp[i] \\times 2^{n-i}\n$$\n\n\nWe approach this problem by considering DP, where $DP[l][i][k]$ represents the number of subsequences of length $l$ up to index $i$ whose sum is $k$. The transitions for this DP can be understood through the "take or not take" approach:\n\n- When considering whether to include the current number $nums[i]$:\n  - If we decide to include it, the transition is $DP[l][i][k] = DP[l-1][i-1][k-nums[i]]$, as we increase the length of the subsequence by 1 and also added $nums[i]$ to the sum of that subsequence with one element less.\n  - If we choose not to include it, the transition is $DP[l][i][k] = DP[l][i-1][k]$, maintaining the previous DP state without considering $nums[i]$.\n\nThe base case is $DP[0][0][0] = 1$, representing the empty subsequence.\n\nWe can also solve this problem iteratively, eliminating one dimension ($i$) for space optimization.\n\n# Complexity\n- Time complexity: $O(n^2 * k)$, where $n$ is the length of `nums` and $k$ is the given target sum.\n- Space complexity: $O(n^3)$ or $O(n^2)$.\n\n# Code\n```python\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n        dp = [[[0]*(k+1) for i in range(n+1)] for i in range(n+1)]\n        \n        dp[0][0][0] = 1\n        mod = 10**9 + 7\n        for i in range(1,n+1):\n            for l in range(0,n+1): \n                for q in range(k+1):\n                    \n                    if q-nums[i-1]>=0 and l :\n                        dp[i][l][q] += dp[i-1][l-1][q-nums[i-1]]\n                        dp[i][l][q] %=mod\n                    \n                    dp[i][l][q] += dp[i-1][l][q]\n                    dp[i][l][q] %= mod\n                        \n        ans  = 0\n        for l in range(1,n+1):\n            ans+=dp[n][l][k]*(2**(n-l))\n            ans%=mod\n\n        return ans\n```\n\n# Space optimized \n\n```python\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n        dp = [[0]*(k+1) for i in range(n+1)]\n        \n        dp[0][0] = 1\n        mod = 10**9 + 7\n        \n        for i in range(1,n+1):\n            ndp = [dp[i].copy() for i in range(n+1)]\n            \n            for l in range(1,n+1): \n                for q in range(k+1):\n                    if q-nums[i-1]>=0:\n                        ndp[l][q] += dp[l-1][q-nums[i-1]]\n                        ndp[l][q] %= mod                    \n                    \n            dp = ndp\n                        \n        ans  = 0\n        for l in range(1,n+1):\n            ans+=dp[l][k]*(2**(n-l))\n            ans%=mod\n\n        return ans\n```
['Python3']