2 Solutions | DFS/Recursion -> Memoization (Top-Down DP)
Solution-1: DFS/Recursion (TLE -- 480 / 577 TCs passed -- 83.18%)\n+ IDEA: Consider all possible subsequences by simulating taking and not taking behavior.\n+ K
# Solution-1: DFS/Recursion (TLE -- 480 / 577 TCs passed -- 83.18%)\n+ **IDEA:** Consider all possible subsequences by simulating taking and not taking behavior.\n+ **KEY:** The key is -- if we obtain the desired sum (k) with lets say `cnt` elements, then it would generate `2^(N-cnt)` subsequences from it. where N-> length of array/subsequence.\n\n### Complexity:\n+ **Time:** O(2^N)\n+ **Space:** O(N)\n###  CODE:\n```\nclass Solution \n{\nprivate:\n    const int MOD = 1e9 + 7;\n    \npublic:\n    int sumOfPower(vector<int>& nums, int k) \n    {\n        // SOL-1: DFS/REC -- TC: O(2^N) SC: O(N) -- TLE -- 480 / 577 TCs passed -- 83.18%\n        return dfs(nums, 0, k, 0);\n    }\n\nprivate:\n    // SOL-1: DFS/REC -- TC: O(2^N) SC: O(N) -- TLE -- 480 / 577 TCs passed -- 83.18%\n    int dfs(vector<int>&nums, int i, int k, int cnt)\n    {\n        if ( k == 0 )\n            return pow(2L, nums.size() - cnt);\n        \n        if ( i>=nums.size() || k < 0 )\n            return 0;\n        \n        int take = dfs(nums, i+1, k-nums[i], cnt+1);\n        int doNotTake = dfs(nums, i+1, k, cnt);\n        return (take + doNotTake)%MOD;\n    }\n\n    int pow (int x, int y)\n    {\n        if (y == 0)\n            return 1;\n        \n        long p = pow(x, y / 2) % MOD;\n        p = (p * p) % MOD;\n        return y % 2 ? (p * x) % MOD : p;\n    }\n};\n```\n# Solution-2: Memoization / Top-Down DP\n+ **IDEA:** The idea is similar to above just that we are storing/memoizing the results to avoid computing the same sub-problems again and again.\n\n### Complexity:\n+ **Time:** O(N * k * N)\n+ **Space:** O(N * k * N)\n\n### CODE:\n```\nclass Solution \n{\nprivate:\n    const int MOD = 1e9 + 7;\n    vector<vector<vector<int>>> dp;\n    \npublic:\n    int sumOfPower(vector<int>& nums, int k) \n    { \n        // SOL-2: MEMOIZATION -- TOP-DOWN DP -- TC: O(N*k*N), SC: O(N*k*N). -- 100% TCs passed.\n        dp = vector<vector<vector<int>>>(nums.size()+1, vector<vector<int>>(k+1, vector<int>(nums.size()+1, -1)));\n        return memo(nums, 0, k, 0);\n    }\n\nprivate:\n    // SOL-2: MEMOIZATION -- TOP-DOWN DP -- TC: O(N*k*N), SC: O(N*k*N). -- 100% TCs passed.\n    int memo(vector<int>&nums, int i, int k, int cnt)\n    {\n        if ( k == 0 )\n            return pow(2L, nums.size() - cnt);\n        \n        if ( i>=nums.size() || k < 0 )\n            return 0;\n        \n        if ( dp[i][k][cnt] != -1 )\n            return dp[i][k][cnt];\n\n        int take = memo(nums, i+1, k-nums[i], cnt+1);\n        int doNotTake = memo(nums, i+1, k, cnt);\n        return dp[i][k][cnt] = (take + doNotTake)%MOD;\n    }\n   \n    int pow (int x, int y)\n    {\n        if (y == 0)\n            return 1;\n        \n        long p = pow(x, y / 2) % MOD;\n        p = (p * p) % MOD;\n        return y % 2 ? (p * x) % MOD : p;\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Recursion', 'Memoization', 'C']