DP | From Basics | Modified Count subseq with sum K
Intuition\n Take example of v = {1, 2, 3} and k = 3. Ans is 6, (3, 1 2, 3, 3, 1 2, 3). Can see that 3 itself is counted multiple times based on the no. of subse
# Intuition\n* Take example of v = {1, 2, 3} and k = 3. Ans is 6, (3, 1 2, 3, 3, 1 2, 3). Can see that 3 itself is counted multiple times based on the no. of subseq of nums it belongs to.\n* So if there is a subseq sub of length m whose sum is k, how many times it will counted in our final ans? it will be 2^(n - m) as no. of subseqs of arr in which sub exists can be calculated as choosing or not choosing every other number that is not a part of sub.\n* Hence, first think to create a dp table, dp[i][j] = sum of power of all subseq ending at id i with their sum j. \n\n# Approach\n* dp[i][j] = sum of power of all subseq ending at id i with their sum j\n* dp[0][0] = binpow(2, n, MOD); as all other elements can be chosen or not chosen (empty subseq belongs to every sub (2^n) of arr)\n* dp[i][j] = summation dp[r][j-nums[i]]/2 for all 0 <= r < i\n* Notice that division by 2 comes beacuse one more element (nums[i]) is fixed in dp[i][j] compared to dp[i][j-nums[i]] and hence the no. of\nsubsequences whose part will be subsequences contributing in dp[i][j] will be half of those contributing in dp[i][j-nums[i]].\n\n# Complexity\n- Time complexity:\nO(n * n * k)\n\n- Space complexity:\nO(n * k)\n\n# Code\n```\n#define ll long long\nclass Solution {\npublic:\n    const int MOD = 1e9 + 7;\n    int sumOfPower(vector<int>& nums, int k) {\n        int n = nums.size();\n        nums.insert(nums.begin(), 0);\n        int dp[n + 1][k + 1];\n        memset(dp, 0, sizeof(dp));\n        dp[0][0] = binpow(2, n, MOD);\n        int inv2 = binpow(2, MOD - 2, MOD);\n        ll ans = 0;\n        for (int i=1; i<=n; ++i){\n            for (int j=0; j<=k; ++j){\n                for (int r = 0; r<i; ++r){\n                    if (j-nums[i] >= 0) dp[i][j] += (1LL * dp[r][j-nums[i]] * inv2) % MOD;\n                    if (dp[i][j] >= MOD) dp[i][j] = dp[i][j] % MOD;\n                }\n            }\n            ans += (dp[i][k]);\n            if (ans >= MOD) ans %= MOD;\n        }\n        return ans ;\n    }\n    int binpow(int a, int b, int MOD){\n        a %= MOD;\n        ll res = 1;\n        while (b > 0){\n            if (b & 1) res = 1LL * res * a % MOD;\n            a = 1LL * a * a % MOD;\n            b >>= 1;\n        }\n        return res;\n    }\n};\n```
['C++']