DP: Clear Code and Concise Explanation (O(n*k) Time, O(n^2*k) Space)
Intuition\nWhen an element is added to a subsequence the length and sum of the subsequence changes. This problem can be formulated as a 2D Dp with length and su
# Intuition\nWhen an element is added to a subsequence the length and sum of the subsequence changes. This problem can be formulated as a 2D Dp with length and sum as the parameters.\n\n# Approach\nCreate a 2D DP of size (n+1)*(k+1)\nfor each index in nums check if any already present subsequence can be extended with nums[index] i.e nums[index] + sum of old subsequence <= k. If it can be done, the new subsequence will have a sum of previous sum + nums[index] and length as old length + 1.\nThe number of new subsequences will be added to the numvber of new subsequences. Take mod 1e9+7 to avoid overflow.\nCaution : We do this in decreasing order of length because otherwise the same element may be counted twice.\n\nNow,when we calculate the count of subsequences with length l and sum s, we iterate over all lengths and check if there are any subsequences with sum s.\nThe contribution by these length l subsequences to the total number of subsequences will be 2^(n-l). Take mod 1e9+7 to avoid overflow.\nThus, we get our answer.dy\n\n# Complexity\n- Time complexity:\n$$O(n^2*k)$$\n\n- Space complexity:\n$$O(n*k)$$\n\n# Code\n```\nclass Solution {\npublic:\n    long long power(int a,int b,int m)\n    {\n        if(b==0) return 1;\n        long long k = power(a,b>>1,m);\n            k = (k*k)%m;\n        if(b&1) k = (k*a)%m;\n        return k;\n    }\n    int sumOfPower(vector<int>& nums, int k) \n    {\n        int n=nums.size();\n        long long count=0,mod=1e9+7;\n        vector<vector<long long>> lensum(n+1,vector<long long> (k+1,0));\n        sort(nums.begin(),nums.end());\n        for(int i=0;i<n;i++)\n        {\n            if(nums[i]>k) break;\n            for(int len=i;len>=1;len--)\n            {\n                for(int j=1;j+nums[i]<=k;j++)\n                {\n                    lensum[len+1][j+nums[i]] += lensum[len][j];\n                    lensum[len+1][j+nums[i]] %= mod;\n                }\n            }\n            if(nums[i]<=k)lensum[1][nums[i]]++;\n        }\n        for(int i=1;i<=n;i++)\n        {\n            if(lensum[i][k] != 0)\n            {\n                count += power(2,n-i,mod)*lensum[i][k];\n                count %= mod;\n            }\n        }\n        return count;\n    }\n};\n```
['Dynamic Programming', 'C++']