[C++] 3D DP Solution, 217ms, 29.98MB
This problem is a fascinating mix of different problems and thus really a good way to train one\'s pattern recognition skills and create something on top of cla
This problem is a fascinating mix of different problems and thus really a good way to train one\'s pattern recognition skills and create something on top of classic ones.\n\nWhile this problem is at its core a DP problem, it also requires us to master a custom implementation of the power function, like [in this famous problem](https://leetcode.com/problems/powx-n/solutions/) ([solved here](https://leetcode.com/problems/powx-n/solutions/739646/c-iterative-vs-recursive-bitwise-solutions-explained-100-time-80-space/)), where apparently a lot of people just go to read the one-liner version and don\'t bother checking the expanded code with explanation\uD83D\uDE44).\n\nWe will also need to figure out which valid subsequences sum up to our `goal` (like we did in [this challenge](https://leetcode.com/problems/target-sum/) [solved here](https://leetcode.com/problems/target-sum/solutions/801164/c-double-dfs-approach-explained-60-time-50-space/)) and how many different probabilities do we have to do so (similar to [this problem](https://leetcode.com/problems/binary-subarrays-with-sum/) [solved here](https://leetcode.com/problems/binary-subarrays-with-sum/solutions/4884508/c-sliding-window-vs-counting-subsequences-of-zeroes-100-time-8ms-80-space-31-12mb/)) - notice that since in this problem we do not need to consider contiguous subsequences, the way we compute our result will change depending on the remaining items, being equal to `2` raised to the power of the remaining ones - since each value can have two states (taken or not).\n\nNow, with that in mind, we want to start running some logic with a branching tree depending on:\n* where in the array to check;\n* what leftover target goal we are giving ourselves;\n* how many elements are left (since this will affect how many permutations we can get, like in the last of the problems mentioned above).\n\nNow, let\'s start coding with a few constants we will use, right after declaring our `resType` as a long:\n* `MOD_VAL` will be our value to cap our results are required in the specs (ie: `1e9 + 7`);\n* `SENTINEL_VALUE` will be our we will flag the cells of `memo` support to know we have not visited them yet.\n\n\nAnd let\'s have them followed by a few instance variables we are going to use:\n* `memo` will be our 3D array to store precomputed results;\n* `nums` will store the original input;\n* `len` will store the length of the original input.\n\nIn our main function, we will `sort` the original vector of elements (this will allow us to `break` out of the main loop when no more values can help us reach `goal` - definitely a good tradeoff for when the time complexity is otherwise already quadratic) populate this variables, then we will `return` the result of calling our helper function `dfs` passing it `0`, `k` and `len`, respectively the starting point `st`, the current `goal` value and the remaining elements we can still use `rem`.\n\nThis function will take its three parameters and:\n* `return` `0` when we are done parsing, either because `st` is equal to `len` or we have no more elements `rem` to use;\n* check if we already computed a value for this scenario, which is to say, if `memo[st][goal][rem]` differs from our `SENTINEL_VALUE`, in which case we will `return` the previously computed one;\n* in our general case, we will:\n    * declare our usual accumulator variable `res` with an initial value of `0`;\n    * loop with `i` from each value in the `[st, len)` interval and, with `newRem` set to be `1` less than `rem`, we will:\n        * store `nums[i]` in `n`;\n        * deal with `3` cases:\n            * when `n > goal`, since `nums` is sorted, it means we can stop parsing here, so we will `break` out of the loop;\n            * when `n == goal` we have a match, so, as explained above, we will increase `res` by `2` raised to the amount of unused elemenets (ie: `newRem`), as computed by our helper function `pow2Mod` (check [here](https://leetcode.com/problems/powx-n/solutions/739646/c-iterative-vs-recursive-bitwise-solutions-explained-100-time-80-space/) to see how it works);\n            * when `n < goal` it means we might be able to use this value, so we are going to increase `res` by the result of calling `dfs` recursively with the next index (ie: `i + 1`), the new goal (ie: `goal - n`) and the new value of the remaining elements (ie: `newRem`);\n    * if `res` exceeds `MOD_VAL`, we will reduce it accordingly;\n    * store `res` in `memo[st][goal][rem]`;\n    * `return` the computed value.\n\n# Complexity\n- Time complexity: $$O(3^n)$$\n- Space complexity: $$O(3^n)$$\n\n# Code\n```cpp\nusing resType = long;\n\nconstexpr resType MOD_VAL = 1000000007;\nconstexpr int SENTINEL_VALUE = -1;\n\nclass Solution {\n    resType memo[100][101][101];\n    vector<int> nums;\n    int len;\n    resType pow2Mod(int base) {\n        // support variables\n        resType multi = 2, res = 1;\n        while (base) {\n            if (base & 1) res *= multi;\n            if (res >= MOD_VAL) res %= MOD_VAL;\n            multi *= multi;\n            if (multi >= MOD_VAL) multi %= MOD_VAL;\n            base >>= 1;\n        }\n        return res;\n    }\n    resType dfs(int st, int goal, int rem) {\n        // base case: no remaining items to use\n        if (st == len || !rem) return 0;\n        // base case, been here before\n        if (memo[st][goal][rem] != SENTINEL_VALUE) return memo[st][goal][rem];\n        // general case\n        // support variables\n        resType res = 0;\n        // parsing nums from st\n        for (int i = st, n, newRem = rem - 1; i < len; i++) {\n            n = nums[i];\n            // stopping when no more matches can be found\n            if (n > goal) break;\n            // noting perfect matches\n            else if (n == goal) res += pow2Mod(newRem);\n            // recurring in all the other cases\n            else res += dfs(i + 1, goal - n, newRem);\n        }\n        while (res >= MOD_VAL) res -= MOD_VAL;\n        return memo[st][goal][rem] = res;\n    }\npublic:\n    int sumOfPower(vector<int> &tmp, int k) {\n        // preparing instance variables\n        memset(memo, SENTINEL_VALUE, sizeof(memo));\n        sort(begin(tmp), end(tmp));\n        swap(nums, tmp);\n        len = nums.size();\n        return dfs(0, k, len);\n    }\n};\n```
['Dynamic Programming', 'Combinatorics', 'C++']