Iterative DP || contribution technique || Easy Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can use contribution technique on all subsequences that sum upto k.\nlet\'s say subs
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can use `contribution technique` on all subsequences that sum upto k.\nlet\'s say subsequence len = 3, total array len = 8 \nthen we can add the contribution of this subsequence by power(2,8-3) = 2^5 (As remaining 5 elements has 2 two choices each) \nIn this way, we can add for all subsequences to reach to the final ans. \n\nNow, comes the part of dp to find all such subsequences that can sum upto k. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n`dp[i][j][k] -> # of subsequences upto ith element such that sum is equal to j and length is k`\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2*k)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n^2*k)$$\n# Code\n```\n#define ll long long\n\nclass Solution {\npublic:\n    const int mod = 1e9+7;\n    ll Powerfun(ll a, ll b){\n        ll ans = 1; \n        while(b>0){\n            if(b&1) ans = (ans*a)%mod;\n            a = (a*a)%mod;\n            b>>=1;\n        }\n        return ans;\n    }\n    \n    int sumOfPower(vector<int>& nums, int k) {\n        // [1,2,3]\n        // 2x2 -> 4\n        // 2 -> 2\n        int n = nums.size();\n        int dp[110][110][110];\n        \n        for(int i=0; i<110; ++i) for(int j=0; j<110; ++j) for(int k=0; k<110; ++k) dp[i][j][k] = 0;\n        \n        dp[0][0][0] = 1;\n        // dp[i][j] -> # of subsequences st upto i elements sum is j & their len is p\n        for(int i=1; i<=k; ++i){\n            dp[0][i][0] = 0;\n        }\n        for(int i=1; i<=n; ++i){\n            dp[i][0][0] = 1;\n        }\n        \n        for(int i=1; i<=n; ++i){\n            for(int j=1; j<=k; ++j){\n                for(int p=1; p<=n; ++p){\n                    int cnt = dp[i-1][j][p];\n                    if(j-nums[i-1]>=0){\n                        cnt = (1ll*cnt + dp[i-1][j-nums[i-1]][p-1])%mod;\n                    }\n                    dp[i][j][p] = cnt;\n                    // cout<<"i: "<<i<<" "<<j<<" "<<p<<" "<<dp[i][j][p]<<endl; \n                }\n            }\n        }\n        int ans = 0; \n        for(int i=1; i<=n; ++i){\n            if(k-nums[i-1]<0) continue;\n            for(int len=1; len<=n; len++){\n                int count = dp[i-1][k-nums[i-1]][len-1];\n            \n                ans = (ans + (count*1ll*Powerfun(2,n-len))%mod)%mod;\n            }\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']