Easy Recursive DP
\n# Complexity\n- Time complexity:\n O(N*N*K) \n\n- Space complexity:\n O(N*N*K)\n\n# Code\n\nclass Solution {\npublic:\n    vector<int> v;\n    int k, n;\n    
\n# Complexity\n- Time complexity:\n<!-- O(N*N*K) -->\n\n- Space complexity:\n<!-- O(N*N*K)-->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> v;\n    int k, n;\n    long long mod = 1000000007;\n    long long int dp[101][101][101];\n    long long power(long long a, long long x) {\n        a %= mod;\n        int res = 1;\n        while (x > 0) {\n            if (x & 1)\n                res = res * a % mod;\n            a = a * a % mod;\n            x >>= 1;\n        }\n        return res;\n    }\n    long long recurse(int idx, int sum, int count) {\n        if (sum == k) {\n            return power((long long)2, (long long)(n - count)) % mod;\n        }\n        if (sum > k || idx >= n) {\n            return 0;\n        }\n        if(dp[idx][sum][count]!=-1){\n            return dp[idx][sum][count];\n        }\n        return dp[idx][sum][count] =  (recurse(idx + 1, sum + v[idx], count + 1) +\n                recurse(idx + 1, sum, count)) %\n               mod;\n    }\n    int sumOfPower(vector<int>& nums, int K) {\n        k = K;\n        n = nums.size();\n        v = nums;\n        memset(dp,-1,sizeof(dp));\n        return recurse(0, 0, 0)%mod;\n    }\n};\n```
['C++']