Dynamic Programming with Memoization
Intuition\nWhen I encountered this problem, I immediately thought about the significance of counting the power of subsequences whose sum equals k. Knowing that 
# Intuition\nWhen I encountered this problem, I immediately thought about the significance of counting the **power** of subsequences whose sum equals `k`. Knowing that direct enumeration would be impractical due to the sheer number of subsequences, I leaned towards **dynamic programming** (DP) as a way to efficiently explore possible sums and subsequences, keeping in mind the need to handle large sums and the modulo constraint.\n\n# Approach\nI decided on a **DP** approach with **memoization** to avoid recalculating the **power** for the same subproblems. The key idea was to:\n\n1.  Use a recursive function that, at each step, decides whether to include the current item in the sum or not, thereby exploring all possible combinations of items.\n2.  If the current sum equals `k`, calculate the **power** of the remaining items (as all their combinations would contribute to the final answer).\n3.  **Memoize** the results to ensure each unique state (defined by the current index, the number of items considered, and the current sum) is calculated only once.\n\nTo optimize further, I utilized a **power**-of-2 function to calculate the number of subsequences dynamically, taking advantage of the fact that the number of subsequences of `n` items is `2^n`.\n\n\n# Complexity\n- Time complexity: The time complexity is difficult to directly quantify due to the recursive nature and memoization. It depends on the number of unique states explored, which is bounded by $O(n * k)$ in the worst case, where $n$ is the length of the `nums` array, and $k$ is the target sum.\n\n\n- Space complexity: $O(n * 105 * 105)$ due to the 3D DP array storing results for each combination of current index, items considered, and current sum. The space complexity is also influenced by the recursion stack depth, which, in the worst case, could be $O(n)$.\n\n# Code\n```\n#define ll long long\nclass Solution {\n  ll powOf2(ll n) {\n    ll p = 1;\n    while (n--) {\n      p = (p * 2) % mod;\n    }\n    return p;\n  }\n\n  ll findSum(ll i, ll item, ll sum, ll k, vector<int> &nums,\n             vector<vector<vector<ll>>> &dp) {\n    if (sum == k) {\n      return powOf2(nums.size() - item);\n    }\n    if (i == nums.size() || sum > k) {\n      return 0;\n    }\n    if (dp[i][item][sum] != -1) {\n      return dp[i][item][sum];\n    }\n    ll take = findSum(i + 1, item + 1, sum + nums[i], k, nums, dp);\n    ll notTake = findSum(i + 1, item, sum, k, nums, dp);\n    return dp[i][item][sum] = (take % mod + notTake % mod) % mod;\n  }\n\npublic:\n  int sumOfPower(vector<int> &nums, int k) {\n    vector<vector<vector<ll>>> dp(nums.size(),\n                                  vector<vector<ll>>(105, vector<ll>(105, -1)));\n    return findSum(0, 0, 0, k, nums, dp);\n  }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']