Simple Intuition Easy || Recursion Dp
Intuition\nThis problem seems to involve calculating the sum of powers of subsets of the given array nums. We can use a recursive approach to iterate over all p
# Intuition\nThis problem seems to involve calculating the sum of powers of subsets of the given array `nums`. We can use a recursive approach to iterate over all possible subsets and calculate the sum of powers for each subset.\n\n# Approach\n1. Define a recursive function `a` that takes the array `nums`, the target sum `k`, the current index `i`, the current sum `sum`, the current subset size `size`, and a memoization array `dp`.\n2. In the base case, if `sum` is equal to `k`, return the power of 2 raised to the power of the difference between `nums.length` and `size` (as each number in the subset can either be included or not, contributing to a total of 2 possibilities for each number).\n3. If `i` is greater than or equal to `nums.length` or `sum` is greater than `k`, return 0.\n4. If the result for the current state `(i, sum, size)` is already calculated, return it from the memoization array `dp`.\n5. Recursively call the `a` function for two cases:\n   - Exclude the current element (`nums[i]`) by calling `a(nums, k, i + 1, sum, size, dp)`.\n   - Include the current element by calling `a(nums, k, i + 1, sum + nums[i], size + 1, dp)`.\n6. Update the memoization array `dp` with the result of the current state and return the sum of the two recursive calls modulo `mod`.\n\n# Complexity\n- Time complexity: Since each element can either be included or excluded, there are 2^n subsets. Therefore, the time complexity is O(2^n), where n is the number of elements in the array `nums`.\n- Space complexity: The space complexity is O(n^3) due to the memoization array `dp` of size 105x105x105, which is used to store the results of overlapping subproblems.\n\n# Code\n```\nclass Solution {\n    int mod=1000000007;\n    public int sumOfPower(int[] nums, int k) {\n        Integer[][][]dp=new Integer[105][105][105];\n        return a(nums,k,0,0,0,dp);\n    }\n    public int a(int[]nums,int k,int i,int sum,int size,Integer[][][]dp){\n        if(sum==k){\n            return (int)(Math.pow(2,nums.length-size)%mod);\n        }\n        if(i>=nums.length || sum>k)return 0;\n        if(dp[i][sum][size]!=null){\n            return dp[i][sum][size];\n        }\n        return dp[i][sum][size]=(a(nums,k,i+1,sum,size,dp)%mod+a(nums,k,i+1,sum+nums[i],size+1,dp))%mod;\n    }\n}\n\n```
['Dynamic Programming', 'Recursion', 'Java']