✅ ⬆️ | Top Down Memoization | DP explore options | Subsequence  | 🔥🔥 [Java]
Top Down\n\nBase Cases:\nThe base case checks if the target sum is 0. If so, there\'s only one way to achieve this sum with an empty subset, so the function ret
**Top Down**\n\n**Base Cases:**\nThe base case checks if the target sum is 0. If so, there\'s only one way to achieve this sum with an empty subset, so the function returns 1.\nIf the idx (index) becomes negative or the target becomes negative, it indicates that we cannot achieve the target sum, so the function returns 0.\n**Memoization:**\nWe use a 2D array memo to store the results of subproblems. memo[idx][target] stores the number of ways to achieve the target sum target using elements from nums[0] to nums[idx].\nBefore calculating a subproblem, we first check if the result is already memoized. If so, we return it directly.\n**Recursive Calls:**\nWe make two recursive calls in each step:\nOne to calculate the number of ways to achieve the target sum without including the current element (waysWithoutCurr).\nAnother to calculate the number of ways to achieve the target sum by including the current element (waysWithCurr).\n**Update Memoization:**\n\nAfter calculating both options, we update the memoization array with the total number of ways considering both cases.\nWe take the modulo of the result to prevent integer overflow.\nReturn Result:\n\nThe result is stored in memo[n - 1][target], where n is the length of the nums array. This represents the number of ways to achieve the target sum using all elements of nums.\nThe function returns this result.\n\n```\nclass Solution {\n    // Define MOD constant\n    final int MOD = 1000000007;\n    \n    public int sumOfPower(int[] nums, int target) {\n        // Get the size of the nums array\n        int n = nums.length;\n        \n        // Initialize memoization array\n        Integer[][] memo = new Integer[n][target + 1];\n        \n        // Call recursive helper function\n        return calculatePower(nums, n - 1, target, memo);\n    }\n    \n    // Recursive helper function to calculate power\n    private int calculatePower(int[] nums, int idx, int target, Integer[][] memo) {\n        // Base case: If target is 0, there\'s one way to achieve the sum with an empty subset\n        if (target == 0) {\n            return 1;\n        }\n        \n        // Base case: If idx is negative or target is negative, return 0\n        if (idx < 0 || target < 0) {\n            return 0;\n        }\n        \n        // If result is already memoized, return it\n        if (memo[idx][target] != null) {\n            return memo[idx][target];\n        }\n        \n        // Exclude current element\n        int waysWithoutCurr = calculatePower(nums, idx - 1, target, memo) % MOD;\n        \n        // Include current element\n        int waysWithCurr = calculatePower(nums, idx - 1, target - nums[idx], memo) % MOD;\n        \n        // Update memoization array with the result\n        memo[idx][target] = (2 * waysWithoutCurr + waysWithCurr) % MOD;\n        \n        // Return the calculated result\n        return memo[idx][target];\n    }\n}\n\n```\n\n\n**Dynamic Approach**\n```\nclass Solution {\n    public int sumOfPower(int[] nums, int target) {\n        // Define MOD constant\n        final int MOD = 1000000007;\n        \n        // Get the size of the nums array\n        int size = nums.length;\n        \n        // Initialize a 2D array to store the dynamic programming results\n        int[][] dp = new int[size + 1][target + 1];\n        \n        // Initialize dp[0][0] to 1, as there is one way to get a sum of 0 with an empty subset\n        dp[0][0] = 1;\n\n        // Perform dynamic programming\n        for (int i = 1; i <= size; ++i) {\n            for (int j = 0; j <= target; ++j) {\n                // Calculate the number of ways to get the sum j without using the current number\n                dp[i][j] = (dp[i - 1][j] * 2) % MOD;\n                \n                // Calculate the number of ways to get the sum j using the current number\n                int diff = j - nums[i - 1];\n                if (diff >= 0) {\n                    dp[i][j] = (dp[i][j] + dp[i - 1][diff]) % MOD;\n                }\n            }\n        }\n\n        // Return the result stored in dp[size][target]\n        return dp[size][target];\n    }\n}\n\n```\n\n**Explanation:**\n\nDefine MOD constant: Define the constant MOD with a value of 1000000007, which represents the modulo value.\nInitialize dp array: Initialize a 2D array dp to store the dynamic programming results. The size of the array is size + 1 rows and target + 1 columns.\nBase case: Set dp[0][0] to 1, as there is one way to get a sum of 0 with an empty subset.\nDynamic programming: Iterate over the nums array and for each number nums[i - 1], and for each possible sum j, calculate the number of ways to achieve the sum j using or not using the current number. Update the dp array accordingly.\nReturn result: Return the result stored in dp[size][target], which represents the number of ways to achieve the target sum using the numbers in the nums array.\n\n![image](https://assets.leetcode.com/users/images/d8e70522-744d-42f0-b3a9-82c4c3d9665c_1708866963.8842509.png)\n\n**Please Upvote**\n
['Java']