[Python] 100% Speed and 100% memory DP with explanation 💯
The power of an array of integers is defined as the number of subsequences with their sum equal to k.  \n\nWe use a for loop to run through all the elements of 
The power of an array of integers is defined as the number of subsequences with their sum equal to k.  \n\nWe use a for loop to run through all the elements of the array, at each step we update \n`num_power`.  `num_power` is an array that holds the number of array for each power(not just `k`). Since a subarray of power `j` where `j<k` can be mapped to a subarray of power `k`, we are going to keep track of all the powers(k and less than that). \n\nWe use dynamic programming to update the `num_power` array. In each step for each new element `num` we face 3 cases:\n\n- `num>k` : For any subarray, the number of subarrays with power p will be doubled. Because: if for power `M` obtained from `[a,b,c]` of subarray `[a,x_1, x_2, b, x_3, ..., c, x_n]` after considering the new element num we can build two subarray that are mapped to  `M` and `[a,b,c]` :    \n\n\t`[a,x_1, x_2, b, x_3, ..., c, x_n]`  \n                          and \n\t`[a,x_1, x_2, b, x_3, ..., c, x_n, num]` \n\t\n\t\n- `num=k` : Similar to the previous case we update the `num_power`, after that since the new element can by itself be a power. We update the `num_power[k]` by all the subsets we can build(which is a power set of all the elements we had so far)\n- `num<k` : In the last case where the new element is less than `k`, after taking a step similar to first bullet point, we need to update not just `num_power[k]` (similar to second bullet point), but also any other `j>= num`. (Any sub array with a power `t=j-num` can be extended to a subarray of power `j`.\n\n\nNote: Since we can be using the power set in step 2 multiple times, I\'ve precomputed it before the loop.\n```\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        MOD = 1_000_000_007\n        k_plus_one = k + 1\n        num_power = [0]*k_plus_one\n        if nums[0]<=k:\n            num_power[nums[0]] = 1\n            \n        two_powers = [1]\n        for i in range(1, len(nums)):\n            two_powers.append((two_powers[-1]*2)%MOD)\n            \n        for i, num in enumerate(nums[1:]):\n            if num > k:\n                #for all the subsets we had so far we have a case either with or without this new element\n                for j in range(1, k_plus_one):\n                    num_power[j] *= 2\n                    num_power[j] %= MOD\n            elif num == k:\n                #for all the subsets we had so far we have a case either with or without this new element\n                for j in range(k_plus_one):\n                    num_power[j] *= 2\n                \n                #sub-subset with the new elements can be only added\n                num_power[num] += two_powers[i+1]\n                num_power[num] %= MOD\n            else:\n                adding = num_power.copy()\n                adding[num] += two_powers[i+1]\n                \n                for j in range(num + 1, k_plus_one):\n                    adding[j] += num_power[j-num]\n                    \n                for j in range(k_plus_one):\n                    num_power[j] += adding[j]\n                    num_power[j] %= MOD\n                                        \n        return num_power[-1]%MOD\n                    \n                    \n                \n```
['Dynamic Programming', 'Python', 'Python3']