2 ^ (N - Count) | 3D - DP
Intuition\nThe problem seems to be related to counting the number of ways to form a certain sum using elements from a given array, where each element can be use
# Intuition\nThe problem seems to be related to counting the number of ways to form a certain sum using elements from a given array, where each element can be used multiple times. The approach might involve dynamic programming to efficiently count the combinations.\n\n# Approach\nThe solution uses dynamic programming (DP) to count the number of ways to form a given sum `k` using elements from the given array `nums`. The `func` function is implemented recursively with memoization. The state `(idx, cnt, sum)` represents the current index being considered, the count of elements chosen so far, and the remaining sum to be achieved. The base cases are:\n- If the sum becomes 0, return `power[n - cnt]` as this represents the number of permutations of the remaining elements (2^(n-cnt)).\n- If the index goes out of bounds or the sum becomes negative, return 0.\nThe function calculates the result by choosing the current element `(nums[idx])` and moving to the next index with a reduced sum or by not choosing the current element and moving to the next index with the same sum. The final result is computed modulo `mod` to avoid integer overflow.\n\n# Complexity\n- Time complexity: `O(n * n * k)`\n- Space complexity: `O(n * n * k)`\n\n# Code\n```\nint mod = 1e9 + 7, power[101];\nint init(){\n    ios_base::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    power[0] = 1;\n    long long int tmp = 1;\n    for(int i = 1; i <= 100; i++) tmp = power[i] = (2 * (tmp % mod)) % mod;\n    return -1;\n}\nint bogus = init();\nclass Solution {\npublic: \n    int dp[101][101][101], n;\n    int func(int idx, int cnt, int sum, vector<int>& nums){\n        if(sum == 0) return power[n - cnt];\n        if(idx == n or sum < 0) return 0;\n        if(dp[idx][cnt][sum] != -1) return dp[idx][cnt][sum];\n        return dp[idx][cnt][sum] = (func(idx + 1, cnt + 1, sum - nums[idx], nums) % mod + func(idx + 1, cnt, sum, nums) % mod) % mod;\n    }\n    int sumOfPower(vector<int>& nums, int k) {\n        n = nums.size();\n        memset(dp, -1, sizeof(dp));\n        return func(0, 0, k, nums);\n    }\n};\n```
['Array', 'Dynamic Programming', 'C++']