Simple explanation using bits | C++ | backtracking | DP
Intuition\nHere, for a n sized array, we have 2^n combinations of subsequences. So we generate all possible subsequences for the given sum k. Now, if you write 
# Intuition\n**Here, for a n sized array, we have 2^n combinations of subsequences. So we generate all possible subsequences for the given sum k. Now, if you write 0 to 2^n - 1 in binary, we get 2^n unique combinations. And if we observe carefully, if we choose any single ith bit, it appears as setbit in exactly 2^n/2 binary representations of a number. Similarly, for any pair, its 2^n/2^2. Hence we conclude if choose any number between 1 and n, it appears in 2^n/2^j. \n**\n\n# Approach\n While checking all subsequences with sum equals to K, we count the no. of elements(j) in the array required for the sum. Hence if we get sum equals to K, we return 2^(n-j). We can use 3D dp with parameters index, sum and count of elements(j).\n\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    long long m = (1e9)+7;\n    long long power(int n){\n        if(n <= 1) return (n+1);\n        long long res = power(n/2);\n        if(n%2) return (((res*res)%m)*2)%m;\n        return ((res*res)%m);\n    }\n\n    long long solve(vector<int>& v, int index, int sum, int j, int&n, vector<vector<vector<int>>>&dp) {\n        if (sum == 0) {\n            return power(n - j);\n        }\n        if (sum < 0 || index == n) return 0;\n        if(dp[index][sum][j] != -1) return dp[index][sum][j];\n        long long take = solve(v, index + 1, sum - v[index], j + 1, n,dp)%m;\n        long long not_take = solve(v, index + 1, sum, j, n,dp)%m;\n        return dp[index][sum][j] = (take + not_take)%m;\n    }\n    \n    int sumOfPower(vector<int>& v, int k) {\n        int n = v.size();\n        vector<vector<vector<int>>>dp(n, vector<vector<int>>(k+1, vector<int>(n+1,-1)));\n        return solve(v, 0, k, 0, n,dp);\n    }\n};\n\n```
['C++']