3d dp answer then optimization to 2d dp , BruteForce => O(n*n*k)  => O(n*k)
Intuition\n\nLets slowly go from understaign the problem => understanding the maths => building the intuition => Bruteforce => o(NNK) => O(nk)\n\nWell basic obs
# Intuition\n\nLets slowly go from understaign the problem => understanding the maths => building the intuition => Bruteforce => o(N*N*K) => O(n*k)\n\nWell basic observation we need to make to make its asking number of subsequences of subsequences with sum equal to k\n//confusing -> simply questions want as find all the subsequence of the array and then sum of number of subsequences of these subsequences whose sum is equal to k\n\nan intersting a observation is if we have to selecte any element say we have to seletect any 3 element from total of 6 elements of array, then\nsay [1,2,3,4,5,6] we have to select 1,3,5 how many such cases will be possible for each of 3 elements left we have 2 options wehter to select them or reject them so it will 2*2*2 ,so 8 ways to select a subsequence which contains all of [1,3,5], in all those 8 cases [1,3,5] will be there\nso we should 8 to answer if we were looking for sum 10, similary other could be [2,3,5] it also has 8 possible parent subsequences whore where it can come, [4,6] has 2*2*2*2 =16 possible parent subsequences similary for others i think you get the point\n\nto sum up  => each subsequence which sums to k will contribute (2^(number elements not selected in that subsequence)) to the answer\ni.e ans+=(2^(selected))\ni.e ans+=(2^(nums.size()-selected));\n\n# Approach\nso now we know the intuition and maths\n\nwe can create a recursive function solve, we need to keep track of index,number of included so far, remaing sum to be achieved\n\nbase case if k==0 we can return answer based on number of elements included\nreturn pow(2,nums.size()-count);\n//base case 2 if we complete the array and still k is not zero than this subsequence is not satisfying the condition so return 0\n\nthere will be recursive case one to take and not take, while taking make sure element is not larger than k\n\nsum the answer of both and return the answer\nTime: 2^(n)\n\nto optimize it we can use a 3d dp\ndp[index][count][k] thus time complexity reduces to O(n*n*k)\nSpace: O(n*n*k)\n//see the solve function in code to see the implementation\n\nsince both k,n<=100 it will pass all the testcases but we can further optimize it O(n*k) for both time and space\n\nto do this instead of keeping track of count(selected elements),\nwe can multipply the answer got from not selecting case by 2 since there is one element which is not selected and then add it to ans\n\n//base1 will be changed to returning the ans based number of elements not selected ahead of last selected element i.e pow(2,nums.size()-index)\n\nrest all will remain same\nnow since we only have two variable index,and k we can use 2d dp which will give \nTime: O(n*k)\nSpace: O(n*k)\n\nsee the solve2d function for implementation\n\n# Complexity\n- Time complexity:\nsolve: O(n*n*k*log(n)) // log(n) for pow function\nsolve2d: O(n*k*logn(n)) //for the 2d dp declared\n\n- Space complexity:\nsolve: O(n*n*k)  // for the 2d dp\nsolve3d: O(n*k) //for the 3d dp\n\n# Code\n```\nclass Solution {\npublic:\n    const int M=1e9+7;\n    int pow(int a,int n){\n        if(n==0) return 1;\n        int temp=pow(a,n/2)%M;\n        temp=(temp*1ll*temp)%M;\n        if(n%2==1){\n            return temp=(temp*1ll*a)%M;\n        }\n        return temp;\n    }\n    int solve(int index,int count,vector<int>& nums,int k,vector<vector<vector<int> > >& dp){\n        if(k==0){\n            return pow(2,nums.size()-count);\n        }\n        if(index==nums.size()){\n            return 0;\n        }\n        if(dp[index][count][k]!=-1) return dp[index][count][k];\n        //not take\n        int ans=solve(index+1,count,nums,k,dp);\n        //take\n        if(nums[index]<=k) {\n            ans=(ans+solve(index+1,count+1,nums,k-nums[index],dp))%M;\n        }\n        return dp[index][count][k]=ans;\n    }\n    int solve2d(int index,int k,vector<int>& nums,vector<vector<int> >& dp){\n        if(k==0){\n            return pow(2,nums.size()-index);\n        }\n        if(index==nums.size()) return 0;\n        if(dp[index][k]!=-1) return dp[index][k];\n        int ans=(2*1ll*solve2d(index+1,k,nums,dp))%M;\n        if(nums[index]<=k){\n            ans+=solve2d(index+1,k-nums[index],nums,dp);\n            ans%=M;\n        }\n        return dp[index][k]=ans;\n    }\n    int sumOfPower(vector<int>& nums, int k) {\n       // vector<vector<vector<int> > > dp(nums.size()+1,vector<vector<int> >(nums.size()+1,vector<int>(k+1,-1)));\n        // int ans=solve(0,0,nums,k,dp);\n        vector<vector<int> > dp(nums.size(),vector<int>(k+1,-1));\n        int ans=solve2d(0,k,nums,dp);\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']