# Find the Sum of the Power of All Subsequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-sum-of-the-power-of-all-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/find-the-sum-of-the-power-of-all-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## 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 _the **sum** of **power** of all subsequences of_ `nums`_._

Since the answer may be very large, return it **modulo** `109 + 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] <= 104`
* `1 <= k <= 100`

# Approaches
## Brute Force with Inner DP
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.
**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.
**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.
### Explanation
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:

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    long MOD = 1_000_000_007;

    public int sumOfPower(int[] nums, int k) {
        int n = nums.length;
        long totalPowerSum = 0;

        // Iterate through all 2^n subsequences of nums using a bitmask
        for (int i = 0; i < (1 << n); i++) {
            List<Integer> subsequence = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                // If the j-th bit is set, include nums[j] in the subsequence
                if ((i & (1 << j)) != 0) {
                    subsequence.add(nums[j]);
                }
            }
            
            // Calculate the power of the current subsequence
            long power = calculatePower(subsequence, k);
            totalPowerSum = (totalPowerSum + power) % MOD;
        }
        
        return (int) totalPowerSum;
    }

    // Calculates the power of a given array (number of its subsequences with sum k)
    private long calculatePower(List<Integer> arr, int k) {
        // dp[j] = number of subsequences with sum j
        long[] dp = new long[k + 1];
        dp[0] = 1; // The empty subsequence has a sum of 0

        for (int x : arr) {
            for (int j = k; j >= x; j--) {
                dp[j] = (dp[j] + dp[j - x]) % MOD;
            }
        }
        
        return dp[k];
    }
}
```
This code will result in a "Time Limit Exceeded" error for larger inputs due to its exponential nature.
### 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.

## Dynamic Programming with Combinatorial Insight
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.
**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.
**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.
### Explanation
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`. 

```java
class Solution {
    public int sumOfPower(int[] nums, int k) {
        long MOD = 1_000_000_007;
        int n = nums.length;

        // dp[j] will store sum_{S' subseq of processed_nums, sum(S')=j} (1/2)^len(S')
        long[] dp = new long[k + 1];
        dp[0] = 1; // For the empty subsequence, sum=0, len=0, (1/2)^0=1

        // Modular inverse of 2, which is (MOD + 1) / 2
        long inv2 = power(2, MOD - 2, MOD);

        for (int x : nums) {
            // Iterate downwards to use dp values from the previous state
            for (int j = k; j >= x; j--) {
                // dp[j] = (ways not using x) + (ways using x)
                // Ways using x: take subsequences summing to j-x, add x.
                // Length increases by 1, so weight is multiplied by 1/2.
                long term = (dp[j - x] * inv2) % MOD;
                dp[j] = (dp[j] + term) % MOD;
            }
        }

        long powerOf2n = power(2, n, MOD);
        long result = (dp[k] * powerOf2n) % MOD;
        
        return (int) result;
    }

    // Helper function for modular exponentiation
    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int sumOfPower(int[] nums, int k) {
    final int mod = (int)1 e9 + 7;
    int n = nums.length;
    int[][] f = new int[n + 1][k + 1];
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= k; ++j) {
        f[i][j] = (f[i - 1][j] * 2) % mod;
        if (j >= nums[i - 1]) {
          f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod;
        }
      }
    }
    return f[n][k];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int sumOfPower(vector<int> &nums, int k) {
    const int mod = 1e9 + 7;
    int n = nums.size();
    int f[n + 1][k + 1];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= k; ++j) {
        f[i][j] = (f[i - 1][j] * 2) % mod;
        if (j >= nums[i - 1]) {
          f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod;
        }
      }
    }
    return f[n][k];
  }
};

```

### Python

```python
class Solution:
    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]

```