[Java/Python 3] Clean T O(n * k) S O(k) DP code using 2 Counters, w/ brief explanation and analysis.
Initialized the Counter cnt as {0:1}, since there is only 1 way to get 0: empty set;\n2. Traverse input nums, for each num, traverse the entries of cnt to get a
1. Initialized the Counter `cnt` as `{0:1}`, since there is only `1` way to get `0`: empty set;\n2. Traverse input `nums`, for each `num`, traverse the entries of `cnt` to get all possible sum (`key + num`) of combinations so far (of course, we only care about the sum that is no greater than `k`); for each `key`, there are `val` ways to get the sum of `key + num`; Further more, since we now have a new item `num`, then each of all current subsequences has a new subsequence: [an old subsequence] + num, hence all values in `cnt` must be doubled.\n3. Modulo all values to `10 ** 9 + 7` according to problem definition.\n\n```java\n    private static final int M = 1_000_000_007;\n    public int sumOfPower(int[] nums, int k) {\n        Map<Integer, Integer> cnt = new HashMap<>(Map.of(0, 1));\n        for (int num : nums) {\n            Map<Integer, Integer> tmp = new HashMap<>();\n            for (var entry : cnt.entrySet()) {\n                int key = entry.getKey(), key1 = num + key, val = entry.getValue();\n                if (key1 <= k) {\n                    tmp.put(key1, (val + tmp.getOrDefault(key1, 0)) % M);\n                }\n            }\n            for (var entry : cnt.entrySet()) {\n                cnt.put(entry.getKey(), 2 * entry.getValue() % M);\n            }\n            for (var entry : tmp.entrySet()) {\n                int key = entry.getKey(), val = entry.getValue();\n                cnt.put(key, (cnt.getOrDefault(key, 0) + val) % M);\n            }\n        }\n        return cnt.getOrDefault(k, 0);\n    }\n```\n\n```python\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        cnt = Counter([0])\n        for num in nums:\n            c = Counter()\n            for key, val in cnt.items():\n                if key + num <= k:\n                    c[key + num] += val\n            for key in cnt.keys():\n                cnt[key] <<= 1\n            cnt.update(c)    \n            for key in cnt.keys():\n                cnt[key] %= 10 ** 9 + 7\n        return cnt[k]\n```\n\n**Analysis:**\nSince  all keys of `cnt` are positive and no greater than `k`, the size of `cnt` is at most `O(k)`; Therefore, for each iteration in the outer for loop, there are at most `O(k)` iterations in inner for loop. As result, `n` iterations of outer for loop * `O(k) = O(n * k)`.\n\nTime: `O(n * k)`, space: `O(min(2 ^ n, k))`.
['Dynamic Programming', 'Java', 'Python3']