Problem

You are given an integer array nums of length n and a positive integer k.

The power of an array of integers is defined as the number of subsequences with their sum equal to k.

Return thesum of power of all subsequences of nums .

Since the answer may be very large, return it modulo 10^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Input: nums = [1,2,3], k = 3

Output: 6

Explanation:

There are `5` subsequences of nums with non-zero power:

  * The subsequence `[_**1**_ ,_**2**_ ,_**3**_]` has `2` subsequences with `sum == 3`: `[1,2,_3_]` and `[_1_ ,_2_ ,3]`.
  * The subsequence `[_**1**_ ,2,_**3**_]` has `1` subsequence with `sum == 3`: `[1,2,_3_]`.
  * The subsequence `[1,_**2**_ ,_**3**_]` has `1` subsequence with `sum == 3`: `[1,2,_3_]`.
  * The subsequence `[_**1**_ ,_**2**_ ,3]` has `1` subsequence with `sum == 3`: `[_1_ ,_2_ ,3]`.
  * The subsequence `[1,2,_**3**_]` has `1` subsequence with `sum == 3`: `[1,2,_3_]`.

Hence the answer is `2 + 1 + 1 + 1 + 1 = 6`.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input: nums = [2,3,3], k = 5

Output: 4

Explanation:

There are `3` subsequences of nums with non-zero power:

  * The subsequence `[_**2**_ ,_**3**_ ,_**3**_]` has 2 subsequences with `sum == 5`: `[_2_ ,3,_3_]` and `[_2_ ,_3_ ,3]`.
  * The subsequence `[_**2**_ ,3,_**3**_]` has 1 subsequence with `sum == 5`: `[_2_ ,3,_3_]`.
  * The subsequence `[_**2**_ ,_**3**_ ,3]` has 1 subsequence with `sum == 5`: `[_2_ ,_3_ ,3]`.

Hence the answer is `2 + 1 + 1 = 4`.

Example 3

1
2
3
4
5
6
7


Input: nums = [1,2,3], k = 7

Output: 0

**Explanation:  **There exists no subsequence with sum `7`. Hence all
subsequences of nums have `power = 0`.

Constraints

  • 1 <= n <= 100
  • 1 <= nums[i] <= 10^4
  • 1 <= k <= 100

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

  1. Initialize a DP array dp of size k+1, where dp[j] is the number of subsequences with sum j.
  2. Set dp[0] = 1 (empty subsequence).
  3. 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].
  4. The answer is dp[k].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        vector<int> dp(k + 1);
        dp[0] = 1;
        for (int x : nums) {
            for (int j = k; j >= x; --j) {
                dp[j] = (dp[j] + dp[j - x]) % MOD;
            }
        }
        return dp[k];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func sumOfPower(nums []int, k int) int {
    mod := int(1e9 + 7)
    dp := make([]int, k+1)
    dp[0] = 1
    for _, x := range nums {
        for j := k; j >= x; j-- {
            dp[j] = (dp[j] + dp[j-x]) % mod
        }
    }
    return dp[k]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int sumOfPower(int[] nums, int k) {
        int MOD = 1_000_000_007;
        int[] dp = new int[k + 1];
        dp[0] = 1;
        for (int x : nums) {
            for (int j = k; j >= x; --j) {
                dp[j] = (dp[j] + dp[j - x]) % MOD;
            }
        }
        return dp[k];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun sumOfPower(nums: IntArray, k: Int): Int {
        val MOD = 1_000_000_007
        val dp = IntArray(k + 1)
        dp[0] = 1
        for (x in nums) {
            for (j in k downTo x) {
                dp[j] = (dp[j] + dp[j - x]) % MOD
            }
        }
        return dp[k]
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def sumOfPower(self, nums: list[int], k: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (k + 1)
        dp[0] = 1
        for x in nums:
            for j in range(k, x - 1, -1):
                dp[j] = (dp[j] + dp[j - x]) % MOD
        return dp[k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn sum_of_power(nums: Vec<i32>, k: i32) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let k = k as usize;
        let mut dp = vec![0; k + 1];
        dp[0] = 1;
        for &x in &nums {
            let x = x as usize;
            for j in (x..=k).rev() {
                dp[j] = (dp[j] + dp[j - x]) % MOD;
            }
        }
        dp[k]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    sumOfPower(nums: number[], k: number): number {
        const MOD = 1e9 + 7;
        const dp = Array(k + 1).fill(0);
        dp[0] = 1;
        for (const x of nums) {
            for (let j = k; j >= x; --j) {
                dp[j] = (dp[j] + dp[j - x]) % MOD;
            }
        }
        return dp[k];
    }
}

Complexity

  • ⏰ Time complexity: O(nk) — For each number, update up to k sums.
  • 🧺 Space complexity: O(k) — For the DP array.