Pick-skip || Number of subset sum problem || C++
Intuition\nIn first testcase-> nums = [1,2,3], k = 3\n1. find the subsequence with sum = k and its length\n    like [1, 2] with len = 2\n2. this subsequence wil
# Intuition\nIn first testcase-> nums = [1,2,3], k = 3\n1. find the subsequence with sum = k and its length\n    like [1, 2] with len = 2\n2. this subsequence will be a part of "number of subset of remaining length" number of subsequences:\n    remaining length, l = TotalLength(n) - len\n    Hence, number of subset of remaining length l = 2 ^ l (cur)\n    i.e., [1, 2] will be part of 2 ^ (3 - 2) = 2\n\n# Code\n```\nclass Solution {\npublic:\n    int mod = 1e9+7, n;\n    int dp[101][101][101];\n        \n    int power(long long x, unsigned int y, int p){\n        int res = 1; \n        x = x % p; \n        if (x == 0) return 0; \n        while (y > 0){\n             if (y & 1)\n                res = (res*x) % p;\n            y = y>>1;\n            x = (x*x) % p;\n        }\n        \n        return res;\n    }\n    \n    \n    int fun(int ind, int sum, int cnt, vector<int> &nums, int k) {\n        if(ind >= n) {\n            if(sum == k) {\n                long cur = power(2, n - cnt, mod) % mod;\n                return cur;\n            }\n            \n            return 0;\n        }\n        \n        if(dp[ind][sum][cnt] != -1) return dp[ind][sum][cnt];\n        \n        long sum1 = fun(ind+1, sum, cnt, nums, k) % mod;\n        long sum2 = 0;\n        if(sum + nums[ind] <= k) sum2 = fun(ind+1, sum+nums[ind], cnt+1, nums, k) % mod;\n        \n        return dp[ind][sum][cnt] = (sum1 + sum2) % mod;\n    }\n    \n    int sumOfPower(vector<int>& nums, int k) {\n        n = nums.size();\n        memset(dp, -1, sizeof(dp));\n        return fun(0, 0, 0, nums, k) % mod;\n    }\n};\n```
['Dynamic Programming', 'C++']