0/1 knapsack
Intuition\nHint 1 : If there is a subsequence of length j with the sum of elements k, it contributes (2 ^ (n - j)) to the answer.\n\nAfter this, it becomes a cl
# Intuition\nHint 1 : If there is a subsequence of length j with the sum of elements k, it contributes (2 ^ (n - j)) to the answer.\n\nAfter this, it becomes a classic take / dontTake DP.\n\ndp[i][len][k] = I\'m starting from index \'i\' with length of the subsequence so far to be \'len\' and I have a target of \'k\' left to make.\n\ndfs(0, 0, k) => starting at index 0, with len 0 and k left.\n\n# Complexity\n- Time complexity:\n        No. of states = n * n * k\n        n possibilities for \'i\'.\n        n possibilities for \'len\' (0 -> n)\n        k possibilities for the target \'k\' (0 -> k)\n\n    And for each of these of states, I\'m either taking or I\'m not taking.\n    This part is O(1).\n\n    => time = O(n * n * k)\n\n- Space complexity: O(n * n * k) + stack space\n\n# Code\n```\ntypedef long long ll;\n\nclass Solution {\npublic:\n    int sumOfPower(vector<int>& nums, int k) {\n        init(nums, k);\n        return dfs(0, 0, k, nums);\n    }\nprivate:\n    int n, k, mod = 1e9 + 7;\n    ll dp[101][101][101];\n\n    void init(auto& nums, int K) {\n        n = nums.size();\n        k = K;\n        memset(dp, -1, sizeof(dp));\n    }\n\n    ll dfs(int i, int len, int k, auto& nums) {\n        if(k == 0) {\n            int power = n - len;\n            return fastPower(2, power);\n        }\n\n        if(k < 0 || i == n) return 0;\n        \n        ll& res = dp[i][len][k];\n        if(res != -1) return res;\n\n        ll take = dfs(i + 1, len + 1, k - nums[i], nums);\n        ll dontTake = dfs(i + 1, len, k, nums);\n\n        return res = (take + dontTake) % mod;\n    }\n\n    ll fastPower(ll x, ll p) {\n        x %= mod;\n        if(x == 0) return 0;\n        ll res = 1;\n        for(ll i = p; i > 0; i /= 2) {\n            if(i % 2) res = (res * x) % mod;\n            x = (x * x) % mod;\n        }\n        return res;\n    }\n};\n```
['Math', 'Memoization', 'C++']