Do not see this dp approach
Bro never forget take, not_take (this is heart of dp)\n# Intuition\nI think from seeing the question similar to generating the subsequences as all of you think 
Bro never forget take, not_take (this is heart of dp)\n# Intuition\nI think from seeing the question similar to generating the subsequences as all of you think \n\n# Approach\nLet\'s discuss with the example [1,2,3] and k=3 and n = 3(size of array)\n1. the subsequences of [1,2,3] with sum==k is [1,2] and [3]\n2. we have to add the remaining elements in this subsequences beacause k==3 can be generate if and only if that elements present in the subsequence.\n3.             [1,2]                            [3]\n        [1,2]         [1,2,3]          [3]            [2,3]\n                                    [3]   [1,3]   [2,3]  [1,2,3]\n4. the [1,2,3] in the left and right part are different because from left subsequence the answer generate is [1,2] and from right part the answer generate is [3]\n5. So the answer from \n   [1,2] = 2 to the power 1    (the remaining element)\n    [3]  = 2 to the power 2  \n\n# Steps\n1. find the count of subsequence element with sum == k\n2. So there is 3 variable index,sum and count (the subsequence element)\n3. the base case is if sum == k or sum+nums[0] == k return pow2[n-count]\n\n\n\n# Code\n```\n#define ll long long int\nclass Solution {\n    ll dp[102][102][102];\n    ll pow2[101]; //store all the 2 power in advance\n    ll mod;\npublic:\n    ll helper(int i,int count,int sum,vector<int>&nums,int k){\n        int n = nums.size();\n        if(sum>k)return 0;\n        if(dp[i][sum][count]!=-1)return dp[i][sum][count];\n        if(i==0){\n            if(sum==k) return pow2[n-count];  //not take\n            if(sum+nums[i] == k) return pow2[n-count+1]; //take (+1 because we take nums[0])\n            return 0;\n        }\n        ll not_take = helper(i-1,count,sum,nums,k);\n        ll take = helper(i-1,count+1,sum+nums[i],nums,k);\n        return dp[i][sum][count] = (not_take%mod + take%mod)%mod;\n\n    }\n    int sumOfPower(vector<int>& nums, int k) {\n        mod = (1e9+7)*1ll;\n        pow2[0]=1;\n        for(int i=1;i<=100;i++){\n            pow2[i]= pow2[i-1]<<1;\n            pow2[i]%=mod;\n        }\n\n        int n = nums.size();\n        memset(dp,-1,sizeof(dp));\n        ll ans = helper(n-1,0,0,nums,k);\n        return (int)ans;\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'C++']