run time and memory both beat 100%, short, easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nWe want to find all subseq summing to k, and for each subseq, calculate number of subse
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe want to find all subseq summing to k, and for each subseq, calculate number of subseq enclosing it - the total number of all such enclosing subseq is answer.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Find all subseq summing to k, output their length. \nSuppose f(i,k) returns list of length for subseq summing to k from nums[i:], then\nf(i,k) = f(i+1,k) + [1 + x for x in f(i+1, k-nums[i])]\nrepresenting the cases of not taking nums[i] and taking nums[i] (if nums[i] <= k)\nExample: nums = [1,2,3], k = 3, f(0,3) = [2,1]\n2. For a subseq summing to k with length L, it is enclosed in 2^(n-L) subseqs. So the final answer is \nsum(2^(n-L) for L in f(0,k))\n3. From the formula in Step 1, we can only store the states for i+1, so a iterative approach should save memory than a recursive approach.\n4. Combining Step 1 and 2, we can further reduce memory to saving the total number of enclosing subseq at (i,k), then \nans(i,k) = ans(i+1, k) + ans(i+1, k-nums[i]) // 2\nhere //2 is because if we include nums[i], then subseq length would add 1, so number of enclosing subseq would divide by 2.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nk)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(k)\n\n# Code\n```\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n\n        ans = [0 for _ in range(k+1)]\n        ans[0] = (1<<n)\n        for i in range(n)[::-1]:\n            cur = [0 for _ in range(k+1)]\n            cur[0] = (1<<n)\n            for s in range(1,k+1):\n                cur[s] = ans[s]\n                if s >= nums[i]:\n                    cur[s] += ans[s-nums[i]] // 2\n\n            ans = cur[:]\n            \n        mm = 10 ** 9 + 7\n        return ans[k] % mm\n        \n```
['Python3']