[C++ / Go] Dynamic Programming - O(nk) solution
Approach\n- d[i][k] is the number of subsequences with their sum equal to k and can use up to first i numbers.\n    - Take nums[i] when k >= nums[i]: d[i - 1][k
# Approach\n- `d[i][k]` is the number of subsequences with their sum equal to `k` and **can** use up to first `i` numbers.\n    - Take `nums[i]` when `k >= nums[i]`: `d[i - 1][k - nums[i]]`\n    - Not take `nums[i]` but still consider `i-th` element : `d[i - 1][k]`\n    - Skip `i-th` element : `d[i - 1][k]` \n\n# Code\n```C++ []\nclass Solution {\nprivate:\n    const int M = 1e9 + 7;\npublic:\n    int sumOfPower(vector<int>& nums, int k) {\n        vector<int> d(k + 1, 0), prev(k + 1, 0);\n\n        prev[0] = 1;\n        for (int num : nums) {\n            for (int i = 0; i <= k; i++) {\n                d[i] = (long long)prev[i] * 2 % M;\n                d[i] %= M;\n\n        \t\tif (i - num >= 0) {\n                    d[i] += prev[i - num];\n                    d[i] %= M;\n                }\n        \t}\n\n            for (int i = 0; i <= k; i++) \n                prev[i] = d[i];\n        }\n\n        return prev[k];\n    }\n};\n```\n```Go []\nconst M = int(1e9 + 7)\n\nfunc sumOfPower(nums []int, k int) int {\n    d := make([]int, k + 1)\n\tprev := make([]int, k + 1)\n\n\tprev[0] = 1\n\tfor _, num := range nums {\n\t\tfor i := 0; i <= k; i++ {\n\t\t\td[i] = (prev[i] * 2) % M\n\t\t\tif i - num >= 0 {\n\t\t\t\td[i] += prev[i-num]\n                d[i] %= M\n\t\t\t}\n\t\t}\n        \n\t\tcopy(prev, d)\n\t}\n\n\treturn prev[k]\n}\n```\n\n# Complexity\n- Time complexity: $O(nk)$\n- Space complexity: $O(k)$
['Dynamic Programming', 'C++', 'Go']