Solution

Method 1 – Dynamic Programming (Subset Sum Counting)

Intuition

For each subsequence, its power is the number of subsequences whose sum is exactly k. The sum of the power of all subsequences is the total number of ways to pick any subset whose sum is k, for all possible subsets. This is a classic subset sum problem, and we can use dynamic programming to count the number of ways to reach each sum.

Approach

Initialize a DP array dp of size k+1, where dp[j] is the number of subsequences with sum j.
Set dp[0] = 1 (empty subsequence).
For each number in nums, update dp from k down to num:
- For each j from k down to num, add dp[j - num] to dp[j].
The answer is dp[k].

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int sumOfPower(vector<int>& nums, int k) {\n        const int MOD = 1e9 + 7;\n        vector<int> dp(k + 1);\n        dp[0]

Related Tags