Easy Solution from Recursion to Top Down Dp(Beats 100%)
Using Recursion (will give TLE)\n# Complexity\n- Time complexity:O(2^N)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(N)\n Add your space 
# Using Recursion (will give TLE)\n# Complexity\n- Time complexity:O(2^N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n```\nclass Solution\n{\n    int mod = (int) 1e9 + 7;\n    private long solve(int[] nums, int sum, int index)\n    {\n        if(index == nums.length) return sum == 0 ? 1 : 0;\n        if(sum < 0) return 0;\n\n        long ans = 0;\n        //take curr element\n        ans += solve(nums, sum- nums[index], index+1);\n\n        //skip\n        ans += solve(nums, sum, index+1)*2;\n\n        if(ans >= mod) ans%=mod;\n        return ans;\n    }\n    public int sumOfPower(int[] nums, int k)\n    {\n        return (int) solve(nums,k,0);\n    }\n}\n```\n\n# Using Top Down Dp(Beats 100%)\n\n# Complexity\n- Time complexity:O(k * N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(k * N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nCode\n```\nclass Solution\n{\n    int mod = (int) 1e9 + 7;\n    private long solve(int[] nums, int sum, int index, long[][] dp)\n    {\n        if(index == nums.length) return sum == 0 ? 1 : 0;\n        if(sum < 0) return 0;\n        if(dp[sum][index] != -1) return dp[sum][index];\n\n        long ans = 0;\n        //take curr element\n        ans += solve(nums, sum- nums[index], index+1, dp);\n\n        //skip\n        ans += solve(nums, sum, index+1, dp)*2;\n\n        if(ans >= mod) ans%=mod;\n        return dp[sum][index] = ans;\n    }\n    public int sumOfPower(int[] nums, int k)\n    {\n        long[][] dp = new long[k+1][nums.length];\n        Arrays.stream(dp).forEach(r->Arrays.fill(r,-1));\n        return (int) solve(nums,k,0, dp);\n    }\n}\n```\n\n![upvote.jpeg](https://assets.leetcode.com/users/images/979c3579-06e0-4743-8bb0-1c896b8b1dab_1710621680.867166.jpeg)\n
['Dynamic Programming', 'Java']