DP top down
Intuition\nEasy dp baby\n\n\n# Complexity\n- Time complexity:\nO(n^3)\n\n- Space complexity:\nO(n^3)\n\n# Code\n\nclass Solution {\npublic:\n    const int mod =
# Intuition\nEasy dp baby\n\n\n# Complexity\n- Time complexity:\n$$O(n^3)$$\n\n- Space complexity:\n$$O(n^3)$$\n\n# Code\n```\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    vector <int> a;\n    int dp[102][102][102];\n    int n;\n    vector <int> powers;\n    int f(int i, int took, int k) {\n        if (k < 0) return 0;\n        if (k == 0) return powers[n - took];\n        if (i == n) return 0;\n        int &res = dp[i][took][k];\n        if (res != -1) return res;\n        res = 0;\n        res = f(i + 1, took, k);\n        res = (res + f(i + 1, took + 1, k - a[i]) % mod) % mod;\n        return res;\n    }\n    int sumOfPower(vector<int>& nums, int k) {\n        a = nums;\n        n = (int) a.size();\n        powers.push_back(1);\n        for (int i = 1; i <= n; ++i) {\n            powers.push_back(powers.back() * 2 % mod);\n        }\n        memset(dp, -1, sizeof dp);\n        return f(0, 0, k);\n    }\n};\n```
['C++']