Find the Sum of the Power of All Subsequences

Hard

#2738Time: O(n * k * 2^n). There are `2^n` subsequences. For each subsequence of average length `n/2`, we perform a DP calculation that takes O((n/2) * k) time. This results in an overall complexity that is prohibitively high.Space: O(n + k). We need O(n) space to store the current subsequence being processed and O(k) space for the dynamic programming table used in the `calculatePower` function.1 company

Patterns

Dynamic Programming

Data structures

Array

Companies

DE Shaw

Prompt

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 the sum of power of all subsequences of nums.

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

Example 1:

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:

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:

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⁴
1 <= k <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. It involves generating every single subsequence of the input array nums. For each of these subsequences, we then calculate its "power" by finding how many of its own subsequences sum to k. The sum of these powers gives the final answer.

Algorithm

Initialize a variable totalPowerSum to 0.
Iterate through all 2^n possible subsequences of the input array nums. A common way to do this is by using a bitmask from 0 to 2^n - 1.
For each integer i in this range, construct the corresponding subsequence S by including nums[j] if the j-th bit of i is set.
For each generated subsequence S, calculate its "power". The power is defined as the number of its own subsequences that sum up to k.
This power calculation is a classic subset sum count problem. It can be solved efficiently using dynamic programming:
- Create a dp array of size k+1, where dp[j] stores the number of subsequences of S that sum to j.
- Initialize dp[0] = 1 (for the empty subsequence) and all other dp entries to 0.
- For each element x in S, update the dp array: for j from k down to x, dp[j] = dp[j] + dp[j-x].
- The power of S is the final value of dp[k].
Add the calculated power to totalPowerSum, taking the result modulo 10^9 + 7.
After iterating through all 2^n subsequences, totalPowerSum will hold the final answer.

Walkthrough

The core of this method is a brute-force enumeration. We generate all 2^n subsequences of nums. For each subsequence, we solve a separate subproblem: find the number of its subsequences that sum to k. This subproblem is a standard dynamic programming task (Subset Sum Count).

Here is the implementation of this approach:

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    long MOD = 1_000_000_007;6 7    public int sumOfPower(int[] nums, int k) {8        int n = nums.length;9        long totalPowerSum = 0;10 11        // Iterate through all 2^n subsequences of nums using a bitmask12        for (int i = 0; i < (1 << n); i++) {13            List<Integer> subsequence = new ArrayList<>();14            for (int j = 0; j < n; j++) {15                // If the j-th bit is set, include nums[j] in the subsequence16                if ((i & (1 << j)) != 0) {17                    subsequence.add(nums[j]);18                }19            }20            21            // Calculate the power of the current subsequence22            long power = calculatePower(subsequence, k);23            totalPowerSum = (totalPowerSum + power) % MOD;24        }25        26        return (int) totalPowerSum;27    }28 29    // Calculates the power of a given array (number of its subsequences with sum k)30    private long calculatePower(List<Integer> arr, int k) {31        // dp[j] = number of subsequences with sum j32        long[] dp = new long[k + 1];33        dp[0] = 1; // The empty subsequence has a sum of 034 35        for (int x : arr) {36            for (int j = k; j >= x; j--) {37                dp[j] = (dp[j] + dp[j - x]) % MOD;38            }39        }40        41        return dp[k];42    }43}

This code will result in a "Time Limit Exceeded" error for larger inputs due to its exponential nature.

Complexity

Time

O(n * k * 2^n). There are `2^n` subsequences. For each subsequence of average length `n/2`, we perform a DP calculation that takes O((n/2) * k) time. This results in an overall complexity that is prohibitively high.

Space

O(n + k). We need O(n) space to store the current subsequence being processed and O(k) space for the dynamic programming table used in the `calculatePower` function.

Trade-offs

Pros

It is a straightforward implementation based on the problem's definition.
It breaks the problem down into smaller, well-known subproblems.

Cons

The time complexity is exponential, making it too slow for the given constraints (n <= 100).
It involves nested loops and recursion/iteration for generating subsequences, leading to complex code.

A much more efficient solution can be found by looking at the problem from a different angle. Instead of iterating through all subsequences S and calculating their power, we can change the order of summation. We consider each subsequence S' of nums that sums to k and count how many larger subsequences S of nums contain S'. This count contributes to the total sum.

Algorithm

The core idea is to rephrase the sum. Instead of summing powers over subsequences S, we sum over subsequences S' that sum to k.
The total sum is sum_{S' subseq of nums, sum(S')=k} 2^(n - len(S')).
This can be rewritten as 2^n * sum_{S' subseq of nums, sum(S')=k} (1/2)^len(S').
We can compute the term sum_{S' subseq of nums, sum(S')=k} (1/2)^len(S') using dynamic programming.
Let dp[j] be the sum of (1/2)^len(S') for all subsequences S' of the numbers processed so far that sum to j.
Initialize a dp array of size k+1 with dp[0] = 1 and others 0.
Calculate the modular multiplicative inverse of 2, inv2.
Iterate through each number x in nums:
- Iterate j from k down to x.
- Update dp[j] by adding the contribution from subsequences that include x. These are formed from subsequences summing to j-x, so their contribution is dp[j-x] * inv2.
- The update rule is dp[j] = (dp[j] + dp[j-x] * inv2) % MOD.
After processing all numbers, dp[k] holds the required sum of weights.
Calculate 2^n % MOD using modular exponentiation.
The final answer is (dp[k] * (2^n % MOD)) % MOD.

Walkthrough

Let's analyze the total sum we need to compute: Sum = sum_{S is a subsequence of nums} power(S). By definition, power(S) is the count of its subsequences S' that sum to k. So, Sum = sum_{S subseq of nums} (sum_{S' subseq of S, sum(S')=k} 1).

By swapping the order of summation, we get: Sum = sum_{S' subseq of nums, sum(S')=k} (sum_{S subseq of nums, S' is subseq of S} 1). The inner sum counts how many subsequences of nums contain a specific S'. If S' has length l, it uses l elements from nums. The remaining n-l elements of nums can either be included or not in a super-subsequence S, giving 2^(n-l) possibilities.

Thus, the formula becomes: Sum = sum_{S' subseq of nums, sum(S')=k} 2^(n - len(S')). We can factor out 2^n to get 2^n * sum_{S' subseq of nums, sum(S')=k} (1/2)^len(S').

This sum can be calculated with dynamic programming. Let dp[j] be the sum of (1/2)^len over all subsequences of elements processed so far that sum to j.

1class Solution {2    public int sumOfPower(int[] nums, int k) {3        long MOD = 1_000_000_007;4        int n = nums.length;5 6        // dp[j] will store sum_{S' subseq of processed_nums, sum(S')=j} (1/2)^len(S')7        long[] dp = new long[k + 1];8        dp[0] = 1; // For the empty subsequence, sum=0, len=0, (1/2)^0=19 10        // Modular inverse of 2, which is (MOD + 1) / 211        long inv2 = power(2, MOD - 2, MOD);12 13        for (int x : nums) {14            // Iterate downwards to use dp values from the previous state15            for (int j = k; j >= x; j--) {16                // dp[j] = (ways not using x) + (ways using x)17                // Ways using x: take subsequences summing to j-x, add x.18                // Length increases by 1, so weight is multiplied by 1/2.19                long term = (dp[j - x] * inv2) % MOD;20                dp[j] = (dp[j] + term) % MOD;21            }22        }23 24        long powerOf2n = power(2, n, MOD);25        long result = (dp[k] * powerOf2n) % MOD;26        27        return (int) result;28    }29 30    // Helper function for modular exponentiation31    private long power(long base, long exp, long mod) {32        long res = 1;33        base %= mod;34        while (exp > 0) {35            if (exp % 2 == 1) {36                res = (res * base) % mod;37            }38            base = (base * base) % mod;39            exp /= 2;40        }41        return res;42    }43}

Complexity

Time

O(n * k). We iterate through each of the `n` numbers in `nums`, and for each, we perform an inner loop of up to `k` iterations.

Space

O(k). We only need a single array of size `k+1` for our dynamic programming state.

Trade-offs

Pros

Highly efficient with a polynomial time complexity.
Solves the problem well within the given constraints.
Uses a standard DP pattern (knapsack-style) once the problem is transformed.

Cons

The combinatorial insight required to transform the problem is not immediately obvious.

Solutions

Solution

1class Solution {2public3  int sumOfPower(int[] nums, int k) {4    final int mod = (int)1 e9 + 7;5    int n = nums.length;6    int[][] f = new int[n + 1][k + 1];7    f[0][0] = 1;8    for (int i = 1; i <= n; ++i) {9      for (int j = 0; j <= k; ++j) {10        f[i][j] = (f[i - 1][j] * 2) % mod;11        if (j >= nums[i - 1]) {12          f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod;13        }14      }15    }16    return f[n][k];17  }18}

1class Solution {2public:3  int sumOfPower(vector<int> &nums, int k) {4    const int mod = 1e9 + 7;5    int n = nums.size();6    int f[n + 1][k + 1];7    memset(f, 0, sizeof(f));8    f[0][0] = 1;9    for (int i = 1; i <= n; ++i) {10      for (int j = 0; j <= k; ++j) {11        f[i][j] = (f[i - 1][j] * 2) % mod;12        if (j >= nums[i - 1]) {13          f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod;14        }15      }16    }17    return f[n][k];18  }19};

1class Solution:2    def sumOfPower(self, nums: List[int], k: int) -> int: mod = 10 ** 9 + 7 n = len(nums) f = [[0] * (k + 1) for _ in range(n + 1)] f[0][0] = 1 for i, x in enumerate(nums, 1): for j in range(k + 1): f[i][j] = f[i - 1][j] * 2 % mod if j >= x: f[i][j] = (f[i][j] + f[i - 1][j - x]) % mod return f[n][k]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem