knapsack DP(easy intuition)
Intuition\n Describe your first thoughts on how to solve this problem. \nIf we find some elements are equal to  sum K . But main idea is in how many subsequence
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf we find some elements are equal to  sum K . But main idea is in how many subsequences these elements will appear .\n To find this lets take an example {1,2,3} K=3 ,\n{1,2} --> leds to 3 . Total number of subsequences of an array is 2^n , (There will be two choices whether to take that element or not). \nHere You must take those two elements in all subsequences so it will become 2^(n-count) -->count =no of elements that sum upto K. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSimple take NotTake DP\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int m = 1e9 + 7;\n    vector<vector<vector<int>>> dp;\n    \n     int power(int x, int y)\n    {\n        if (y == 0)\n            return 1LL;\n        else if (y % 2 == 0)\n            return 1LL * power(x, y / 2) * power(x, y / 2)%m;\n        else\n            return  1LL* x * power(x, y / 2) * power(x, y / 2)%m;\n    }\n    \n    long long solve(vector<int>& nums, int k, int i, int sum, int count){\n        if(sum == k) {\n            return power(2,nums.size() - count);\n        }\n        if(i >= nums.size() || sum > k ) return 0;\n        if(dp[i][count][sum] != -1) return dp[i][count][sum];\n        \n        long long take = solve(nums, k, i + 1, sum + nums[i], count + 1);\n        long long notTake = solve(nums, k, i + 1, sum, count);\n        return dp[i][count][sum] = (take + notTake)%m;\n    }\n    \n    int sumOfPower(vector<int>& nums, int k) {\n        dp.resize(100, vector<vector<int>>(101, vector<int>(101, -1)));\n        return solve(nums, k, 0, 0, 0);\n    }\n};\n```
['C++']