Dynamic Programming Approach | Finding all the subsequence and applying counting formula | ✅✅
Problem Overview:\nWe\'re given an array of integers nums and an integer k. We need to find the sum of powers of 2 for all possible subsequences of nums whose s
# Problem Overview:\nWe\'re given an array of integers nums and an integer k. We need to find the sum of powers of `2` for all possible subsequences of nums whose sum equals k. We want to return this sum modulo `10^9 +7`.\n\n# Intuition\n\n- Brute Force Approach : We could iterate through all possible subsequences of nums and calculate the sum of powers of 2 for each subsequence whose sum equals k.\nHowever, this approach would be highly inefficient as the number of subsequences grows exponentially with the size of nums.\n\n- Dynamic Programming with Memoization : We can use dynamic programming with memoization to optimize our solution.\nBy keeping track of the sum of powers of 2 for each possible sum from 0 to k, we can efficiently compute the sum for all possible subsequences.\n\n# Approach\nTo solve this problem, we can use dynamic programming. We define a recursive function solve that calculates the sum of powers of 2 for all possible subsequences starting from index i with current sum sum and count of elements included in the subsequence count. We memoize the results using a 3D dp array dp.\n\nWe iterate through each element of the array nums and for each element, we have two choices: either include it in the subsequence or skip it. We recursively call the solve function for both choices and update the dp array accordingly.\n\nFinally, we return the result obtained from the solve function for the initial state where i = 0, sum = 0, and count = 0.\n\n\n# Detailed Explanation:\n\n- Recursive Function: We\'ll define a recursive function solve that explores all possible subsequences starting from a specific index i, with a current sum sum, and a count of elements included in the subsequence count.\nThe function will return the sum of powers of 2 for all valid subsequences.\n\n- Base Case: If the current sum sum equals k, we return \n2^(n\u2212count), where n is the size of nums and count is the number of elements included in the subsequence.\nIf the index i exceeds the size of nums, or the current sum sum exceeds k, we return 0.\n\n\n- Recursive Case: \n\nWe consider two choices for the current element nums[i]:\nInclude nums[i] in the subsequence: We recursively call solve with i+1, sum+nums[i], and count+1.\nExclude nums[i] from the subsequence: We recursively call solve with i+1, sum, and count.\nWe sum up the results from both choices.\n\n- Memoization:\n\nWe use memoization to store and retrieve the results of subproblems efficiently.\nWe maintain a memoization table indexed by the current sum sum and the count of elements included in the subsequence count.\nBefore making a recursive call, we check if the result for the current subproblem is already calculated and stored in the memoization table. If so, we return it directly.\n\n- Final Steps:\n\nWe initialize the memoization table with appropriate dimensions.\nWe call the solve function with the initial parameters i=0, sum=0, and count=0.\nWe return the result obtained from the solve function.\n\n\n# Complexity\n\n- Time complexity: O(N * K), where N is the number of elements in the array nums and K is the target sum.\n\n- Space complexity: O(N * K) due to the memoization array dp.\n\n# Code\n```\nclass Solution\n{\npublic:\n    const int MOD = 1e9 + 7;\n\n    long long powMod(long long base, long long exp, long long mod)\n    {\n        long long result = 1;\n        while (exp > 0)\n        {\n            if (exp % 2 == 1)\n            {\n                result = (result * base) % mod;\n            }\n            base = (base * base) % mod;\n            exp /= 2;\n        }\n        return result;\n    }\n\n    long long solve(vector<int> &nums, int k, int idx, vector<int> &vec, vector<vector<vector<long long>>> &memo)\n    {\n        if (k == 0)\n        {\n            return powMod(2, (long long)(nums.size() - vec.size()), MOD);\n        }\n\n        if (memo[k][idx][vec.size()] != -1)\n        {\n            return memo[k][idx][vec.size()];\n        }\n\n        long long ans = 0;\n        for (int i = idx; i < nums.size(); i++)\n        {\n            if (nums[i] > k)\n                break;\n            vec.push_back(nums[i]);\n            ans += solve(nums, k - nums[i], i + 1, vec, memo);\n            ans %= MOD;\n            vec.pop_back();\n        }\n\n        memo[k][idx][vec.size()] = ans;\n        return ans;\n    }\n\n    int sumOfPower(vector<int> &nums, int k)\n    {\n        vector<int> vec;\n        sort(nums.begin(), nums.end());\n        int n = k + 1;\n        vector<vector<vector<long long>>> memo(n, vector<vector<long long>>(nums.size() + 1, vector<long long>(nums.size() + 1, -1)));\n        return solve(nums, k, 0, vec, memo);\n    }\n};\n\n```
['Dynamic Programming', 'C++']