3082. Find the Sum of the Power of All Subsequences Solution - ( Brute Force to efficient Solution)
Overview\nWe are provided with an array of length n and a positive integer k. The power of the array is defined as the number of subsequences having a sum equal
# Overview\nWe are provided with an array of length n and a positive integer k. The power of the array is defined as the number of subsequences having a sum equal to k. Our task is to return the sum of the powers of all such subsequence modulo 1000000007.\n\n# Approach 1: Brute force \n# Intuition: \nFirstly, we understand that the power of an array is defined as the number of subsequences having a sum equal to k. \n\nTo achieve this, we iterate through all possible subsequence and check if their sum equals k. If the sum equals k, we know that this subsequence contributes to the sum of k. Therefore, we need to count all other subsequences that contain this specific subsequence. \n\nThis count can be calculated using the formula power(2, n - cnt), where n is the total number of elements in the array and cnt denotes the count of elements in that subsequence that produced the sum equal to k.\n\n Similarly, we calculate the sum of the powers of all subsequences having a sum equal to k.\n\n\n# Algorithm: \nWe recursively try out all possible subsequences starting from every index. From a given index i, we have two choices: either to include this index in the subsequence sum or not.\n1.\tIf we include the i-th index in the subsequence, then we decrease the value of k to k - nums[i] and increment the cnt variable to cnt + 1, as we include the given element in the subsequence.\n\n2.\tIf we don\u2019t include the i-th index in the sum, then the values of k and cnt remain the same.\n\nWhen the value of k becomes 0, we return the number of subsequences that can contain this specific sequence, which is calculated as power(2, n - cnt). \n\nIf k is less than or equal to 0, or if i equals n, we return 0.\n\n\n# Implementation:\n\n C++:\n ```\n class Solution\n{\npublic:\n    int n, mod = 1e9 + 7;\n    int power(int cnt)\n    {\n        int val = 1;\n        for (int j = 0; j < n - cnt; j++)\n        {\n            val = (val * 2) % mod;\n        }\n        return val;\n    }\n    int solve(int i, int k, int cnt, vector<int> &nums)\n    {\n        if (k < 0)\n            return 0;\n        if (k == 0)\n        {\n            int val = power(cnt);\n            return val;\n        }\n        if (i == n)\n        {\n            return 0;\n        }\n        int ans;\n        ans = solve(i + 1, k - nums[i], cnt + 1, nums);\n        ans = (ans + solve(i + 1, k, cnt, nums)) % mod;\n        return ans;\n    }\n    int sumOfPower(vector<int> &nums, int k)\n    {\n        n = nums.size();\n        return solve(0, k, 0, nums);\n    }\n};\n```\n\nJava :\n```\nclass Solution\n{\n    int n;\n    int mod = 1000000007;\n\n    int power(int cnt)\n    {\n        int val = 1;\n        for (int j = 0; j < n - cnt; j++)\n        {\n            val = (val * 2) % mod;\n        }\n        return val;\n    }\n\n    int solve(int i, int k, int cnt, int[] nums)\n    {\n        if (k < 0)\n            return 0;\n        if (k == 0)\n        {\n            int val = power(cnt);\n            return val;\n        }\n        if (i == n)\n        {\n            return 0;\n        }\n        int ans;\n        ans = solve(i + 1, k - nums[i], cnt + 1, nums);\n        ans = (ans + solve(i + 1, k, cnt, nums)) % mod;\n        return ans;\n    }\n\npublic\n    int sumOfPower(int[] nums, int k)\n    {\n        n = nums.length;\n        return solve(0, k, 0, nums);\n    }\n}\n\n```\n\nPython:\n```\nclass Solution(object):\n    def power(self, cnt):\n        mod = 1000000007\n        val = 1\n        for j in range(self.n - cnt):\n            val = (val * 2) % mod\n        return val\n\n    def solve(self, i, k, cnt, nums):\n        mod = 1000000007\n        if k < 0:\n            return 0\n        if k == 0:\n            val = self.power(cnt)\n            return val\n        if i == self.n:\n            return 0\n        ans = self.solve(i + 1, k - nums[i], cnt + 1, nums)\n        ans = (ans + self.solve(i + 1, k, cnt, nums)) % mod\n        return ans\n\n    def sumOfPower(self, nums, k):\n        self.n = len(nums)\n        return self.solve(0, k, 0, nums)\n```\n\n\n# Complexity Analysis:\nLet n be the length of array \n\n**Time complexity:**  O(2^n)\nDue to 2 possible recursive calls at each index\n\n**Space complexity:**  O(n) \nDue to the recursive stack space while calling each recursive calls.\nThe brute force approach is unable to pass all test cases within the given constraints.\n\n\n\n\n# Approach 2: Memoization (Dynamic Programming)\n\n# Intuition: \nThe power of an array is defined as the number of subsequences having a sum equal to k. To compute this efficiently, we utilize dynamic programming. \nWe create a three-dimensional dp array to store the number of subsequences that can be formed up to a certain index, with a certain sum, and including a certain count of elements that produced the sum equal to k. We iterate through each element of the array and update the dp array accordingly.\n\nFor each element in the array, we consider two possibilities: either we include the current element in the subsequence sum or we don\'t. If we include the element, we decrement the remaining sum by the value of the current element and increment the count of elements that produced the sum equal to k. We recursively explore both possibilities, updating the dp array with the results.\n\nIf the remaining sum becomes zero, we know we\'ve found a valid subsequence. We calculate the count of all other subsequences containing this specific subsequence using the formula power(2, n - cnt), where n is the total number of elements in the array and cnt denotes the count of elements that produced the sum equal to k.\n\nBy memoizing the results of subproblems in the dp array, we ensure that each subproblem is solved only once, avoiding redundant computations and leading to an efficient solution for computing the sum of powers of all subsequences having a sum equal to k.\n\n# Algorithm: \nWe use Memoization to store the results of subproblems to avoid redundant computations.\n\n1.\tWe initialize a three-dimensional dp array to store the number of subsequences that can be formed up to a certain index, with a certain sum, and including a certain count of elements that produced the sum equal to k with -1 initially .\n\n2.\tWe recursively explore all possible subsequences starting from every index.\n\n3.\tAt each index I, we have two choices:\n\t\t\u2022\tInclude the i-th index in the subsequence sum:\n\t\t\u2022\tDecrement the value of k to k \u2013 nums[i].\n\t\t\u2022\tIncrement the cnt variable to cnt + 1, as we include the given element in the subsequence.\n\t\t\u2022\tExclude the i-th index from the sum:\n\t\t\u2022\tThe values of k and cnt remain the same.\n4.\tIf the value of k becomes 0, we know we\u2019ve found a valid subsequence. We calculate the count of all other subsequences containing this specific subsequence using the formula power(2, n \u2013 cnt), where n is the total number of elements in the array and cnt denotes the count of elements that produced the sum equal to k.\n\n5.\tWe Memoize the results of subproblems in the dp array.\n\n6.\tIf at any point the dp[index][k][cnt] is not equal to -1 means this subproblem already calculated  so we return that value dp[index][k][cnt].\n\n7.\tIf k is less than or equal to 0, or if I equals n, we return 0.\n\n  # Implementation:\n\n     C++:\n   ```\nclass Solution\n{\npublic:\n    int n, mod = 1e9 + 7;\n    int dp[101][101][101];\n    int power(int cnt)\n    {\n        int val = 1;\n        for (int j = 0; j < n - cnt; j++)\n        {\n            val = (val * 2) % mod;\n        }\n        return val;\n    }\n    int solve(int i, int k, int cnt, vector<int> &nums)\n    {\n        if (k < 0)\n            return 0;\n        if (k == 0)\n        {\n            int val = power(cnt);\n            return val;\n        }\n        if (i == n)\n        {\n            return 0;\n        }\n        if (dp[i][cnt][k] != -1)\n            return dp[i][cnt][k];\n        int ans;\n        ans = solve(i + 1, k - nums[i], cnt + 1, nums);\n        ans = (ans + solve(i + 1, k, cnt, nums)) % mod;\n        return dp[i][cnt][k] = ans;\n    }\n    int sumOfPower(vector<int> &nums, int k)\n    {\n        n = nums.size();\n        memset(dp, -1, sizeof(dp));\n        return solve(0, k, 0, nums);\n    }\n};\n```\n  Java:\n```\nimport java.util.Arrays;\n\npublic class Solution {\n    int n;\n    int mod = 1000000007;\n    int[][][] dp = new int[101][101][101];\n\n    public int power(int cnt) {\n        int val = 1;\n        for (int j = 0; j < n - cnt; j++) {\n            val = (val * 2) % mod;\n        }\n        return val;\n    }\n\n    public int solve(int i, int k, int cnt, int[] nums) {\n        if (k < 0)\n            return 0;\n        if (k == 0) {\n            int val = power(cnt);\n            return val;\n        }\n        if (i == n) {\n            return 0;\n        }\n        if (dp[i][cnt][k] != -1)\n            return dp[i][cnt][k];\n        int ans;\n        ans = solve(i + 1, k - nums[i], cnt + 1, nums);\n        ans = (ans + solve(i + 1, k, cnt, nums)) % mod;\n        return dp[i][cnt][k] = ans;\n    }\n\n    public int sumOfPower(int[] nums, int k) {\n        n = nums.length;\n        for (int[][] d2 : dp) {\n            for (int[] d1 : d2) {\n                Arrays.fill(d1, -1);\n            }\n        }\n        return solve(0, k, 0, nums);\n    }\n}\n```\nPython:\n\n```\n\nfrom typing import List\n\nclass Solution:\n    def __init__(self):\n        self.dp = [[[None] * 101 for _ in range(101)] for _ in range(101)]\n        self.mod = 1000000007\n\n    def power(self, cnt):\n        val = 1\n        for j in range(self.n - cnt):\n            val = (val * 2) % self.mod\n        return val\n\n    def solve(self, i, k, cnt, nums):\n        if k < 0:\n            return 0\n        if k == 0:\n            val = self.power(cnt)\n            return val\n        if i == self.n:\n            return 0\n        if self.dp[i][cnt][k] is not None:\n            return self.dp[i][cnt][k]\n        ans = self.solve(i + 1, k - nums[i], cnt + 1, nums)\n        ans = (ans + self.solve(i + 1, k, cnt, nums)) % self.mod\n        self.dp[i][cnt][k] = ans\n        return ans\n\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        self.n = len(nums)\n        for d2 in self.dp:\n            for d1 in d2:\n                d1[:] = [None] * 101\n        return self.solve(0, k, 0, nums)\n    \n\t```\n\n\n# Complexity Analysis:\nLet n be the length of array \n\n**Time complexity:**  O(n*k*n)\nThere are total n states and the maximum possible value of cnt can be n.\n\n**Space complexity:**  O(n*k*n)\nTo store the all states of recursion we need an extra dp array of size n*m*n;\n\n\n\n\n\n
['C', 'Python']