DP || Simple Code || C++
Intuition\nIf there is a subsequence of length j with the sum of elements k, it contributes 2^(n-j) to the answer.\n# Code\n\nclass Solution \n{\npublic:\n    i
# Intuition\nIf there is a subsequence of length j with the sum of elements k, it contributes 2^(n-j) to the answer.\n# Code\n```\nclass Solution \n{\npublic:\n    int mod=1e9+7;\n    int dp[101][101][101];\n    int f(int i, vector<int> &nums, int cnt, int sum, int k)\n    {\n        if(sum==k)\n        {\n            int p=1;\n            for(int x=0; x<nums.size()-cnt; x++)\n            {\n                p=((long long)p*2)%mod;\n            }\n            return p;\n        }\n        if(sum>k || (i==nums.size())) return 0;\n        if(dp[i][cnt][sum]!=-1) return dp[i][cnt][sum];\n        int take=f(i+1,nums,cnt+1,sum+nums[i],k);\n        int dont=f(i+1,nums,cnt,sum,k);\n        return dp[i][cnt][sum]=((long long)take+dont)%mod;\n    }\n    int sumOfPower(vector<int>& nums, int k) \n    {\n        memset(dp,-1,sizeof(dp));\n        return f(0,nums,0,0,k);\n    }\n};\n```
['Dynamic Programming', 'C++']