# Find the Sum of Subsequence Powers
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-sum-of-subsequence-powers)
Canonical: https://scaleengineer.com/dsa/problems/find-the-sum-of-subsequence-powers
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
You are given an integer array `nums` of length `n`, and a **positive** integer `k`.

The **power** of a subsequence is defined as the **minimum** absolute difference between **any** two elements in the subsequence.

Return _the **sum** of **powers** of **all** subsequences of_ `nums` _which have length_ **_equal to_** `k`.

Since the answer may be large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** nums = \[1,2,3,4\], k = 3

**Output:** 4

**Explanation:**

There are 4 subsequences in `nums` which have length 3: `[1,2,3]`, `[1,3,4]`, `[1,2,4]`, and `[2,3,4]`. The sum of powers is `|2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4`.

**Example 2:**

**Input:** nums = \[2,2\], k = 2

**Output:** 0

**Explanation:**

The only subsequence in `nums` which has length 2 is `[2,2]`. The sum of powers is `|2 - 2| = 0`.

**Example 3:**

**Input:** nums = \[4,3,-1\], k = 2

**Output:** 10

**Explanation:**

There are 3 subsequences in `nums` which have length 2: `[4,3]`, `[4,-1]`, and `[3,-1]`. The sum of powers is `|4 - 3| + |4 - (-1)| + |3 - (-1)| = 10`.

**Constraints:**

* `2 <= n == nums.length <= 50`
* `-108 <= nums[i] <= 108 `
* `2 <= k <= n`

# Approaches
## Approach 1: Direct DP with Power Distribution
This approach uses dynamic programming to directly build the distribution of powers for subsequences of increasing lengths. We define a DP state that stores not just a single value, but a map from each possible power value to the count of subsequences having that power.
**Time:** O(k * n^2 * D), where D is the number of distinct power values. In the worst case, D is O(n^2), leading to a time complexity of O(k * n^4). Given n <= 50, this might be too slow but could pass if the number of distinct powers is small in practice. · **Space:** O(k * n * D), where D is the number of distinct power values. In the worst case, D can be O(n^2), leading to a space complexity of O(k * n^3).
**Pros:** It's a direct and intuitive DP formulation of the problem.; It correctly solves the problem without complex combinatorial identities.
**Cons:** The time complexity is high, making it potentially slow for the given constraints, though it might just pass.; The space complexity is also significant due to storing maps for each DP state.
### Explanation
The core idea is to compute, for each length `j` and ending element `nums[i]`, how many subsequences have a certain power. We can define `dp[i][j]` as a hash map, where keys are power values and values are the counts of subsequences of length `j` ending at `nums[i]` with that power.

To compute `dp[i][j]`, we iterate through all possible previous elements `nums[p]` (`p < i`). For each `p`, we look at the power distributions of subsequences of length `j-1` ending at `p`, which is `dp[p][j-1]`. For each `(old_power, count)` pair in `dp[p][j-1]`, we form a new subsequence by adding `nums[i]`. The new power will be `min(old_power, nums[i] - nums[p])`. We update the map `dp[i][j]` with this new information.

After computing these distributions for all `i` and for `j=k`, the final answer is obtained by summing up `power * count` over all these distributions.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int sumOfPowers(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long MOD = 1_000_000_007;

        // dp[i][j] is a map from power to count for subsequences of length j ending at nums[i]
        Map<Integer, Long>[][] dp = new HashMap[n][k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j] = new HashMap<>();
            }
        }

        // Base case: subsequences of length 1
        for (int i = 0; i < n; i++) {
            dp[i][1].put(Integer.MAX_VALUE, 1L); // Power is effectively infinite
        }

        for (int len = 2; len <= k; len++) {
            for (int i = len - 1; i < n; i++) {
                for (int p = len - 2; p < i; p++) {
                    int diff = nums[i] - nums[p];
                    for (Map.Entry<Integer, Long> entry : dp[p][len - 1].entrySet()) {
                        int oldPower = entry.getKey();
                        long count = entry.getValue();
                        int newPower = Math.min(oldPower, diff);
                        dp[i][len].put(newPower, (dp[i][len].getOrDefault(newPower, 0L) + count) % MOD);
                    }
                }
            }
        }

        long totalSumOfPowers = 0;
        for (int i = k - 1; i < n; i++) {
            for (Map.Entry<Integer, Long> entry : dp[i][k].entrySet()) {
                long power = entry.getKey();
                long count = entry.getValue();
                totalSumOfPowers = (totalSumOfPowers + (power * count) % MOD) % MOD;
            }
        }

        return (int) totalSumOfPowers;
    }
}
```
### Algorithm
1. **Sort the Input Array**: First, sort the `nums` array in non-decreasing order. This simplifies the calculation of differences, as `|a - b|` becomes `b - a` for `a < b`. The set of subsequences remains the same, only their element order might change, which doesn't affect the power calculation.
2. **Define DP State**: Let `dp[i][j]` be a map where `dp[i][j][p]` stores the number of subsequences of length `j` that can be formed using elements from `nums[0...i]`, with `nums[i]` being the largest element, and having a power of exactly `p`.
3. **Base Case**: For subsequences of length 1, the power is undefined. We can consider it to be infinite. So, for each `i` from 0 to `n-1`, `dp[i][1]` will be a map `{ infinity: 1 }`.
4. **DP Transition**: We build the solution for length `j` from `2` to `k`. To compute `dp[i][j]`, we consider `nums[i]` as the largest element. The second largest element must be `nums[p]` for some `p < i`. The remaining `j-2` elements must be chosen from `nums[0...p-1]`.
   - A subsequence of length `j` with `nums[i]` as the max and `nums[p]` as the second max is formed by taking a subsequence of length `j-1` ending at `nums[p]` and appending `nums[i]`.
   - Let `S'` be a subsequence of length `j-1` ending at `nums[p]`. Its power is `power(S')`. The new subsequence `S = S' ∪ {nums[i]}` has `power(S) = min(power(S'), nums[i] - nums[p])`.
   - We iterate through `p` from `j-2` to `i-1`. For each `p`, we iterate through the power distribution map `dp[p][j-1]`. For each entry `(power_old, count)` in `dp[p][j-1]`, the new power is `min(power_old, nums[i] - nums[p])`. We add `count` to the corresponding entry in `dp[i][j]`'s map.
5. **Calculate Total Sum**: After filling the `dp` table up to length `k`, the total sum of powers is the sum of `power * count` for all entries in all `dp[i][k]` maps, for `i` from `k-1` to `n-1`. All calculations should be done modulo `10^9 + 7`.

## Approach 2: DP over Differences
A more efficient approach transforms the problem. Instead of summing the powers directly, we sum the counts of subsequences that meet a certain power threshold. The sum of powers of all subsequences `S` is equal to the sum, over all possible positive integers `d`, of the number of subsequences with power greater than or equal to `d`.

The values of `d` for which this count changes are precisely the differences `nums[j] - nums[i]`. This allows us to discretize the problem. We only need to calculate the count for each unique difference value.
**Time:** O(n^2 * log(n^2) + D * n * k), where D is the number of unique differences. D can be up to O(n^2). The dominant part is `D * n * k`, leading to a total complexity of O(n^3 * k). · **Space:** O(n^2 + n*k). O(n^2) to store the unique differences and O(n*k) for the DP table in the helper function.
**Pros:** Significantly more efficient than the direct DP approach.; The complexity is well within the limits for the given constraints.
**Cons:** The logic is more complex, relying on a combinatorial identity and a DP on top of it.; Implementation requires careful handling of several nested loops and data structures.
### Explanation
First, we sort the `nums` array. The main insight is to change the summation: `Sum(power(S)) = Sum_{d > 0} (count of subsequences with power >= d)`. Since the count of subsequences with power `>= d` is a step function that only changes at values `d = nums[j] - nums[i]`, we can compute the sum more efficiently.

Let `v_1, v_2, ..., v_m` be the unique sorted positive differences. The total sum is `(v_1 - v_0)*N(>=v_1) + (v_2 - v_1)*N(>=v_2) + ...`, where `v_0 = 0` and `N(>=v)` is the number of subsequences of length `k` with power at least `v`.

For each required `v`, we can compute `N(>=v)` using an `O(n*k)` dynamic programming algorithm. Let `dp[i][j]` be the number of valid subsequences of length `j` using elements from `nums[0...i-1]` and ending with `nums[i-1]`. To form such a subsequence, we must pick a previous element `nums[p-1]` such that `nums[i-1] - nums[p-1] >= v`. The number of ways is the sum of `dp[p][j-1]` over all valid `p`. This sum can be optimized using prefix sums and a two-pointer approach to achieve `O(n*k)` complexity for each `v`.

Since there are `O(n^2)` unique differences, the total time complexity becomes `O(n^2 * n * k) = O(n^3 * k)`.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    long MOD = 1_000_000_007;

    public int sumOfPowers(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;

        Set<Integer> diffSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                diffSet.add(nums[j] - nums[i]);
            }
        }
        List<Integer> diffs = new ArrayList<>(diffSet);
        Collections.sort(diffs);

        long totalSum = 0;
        long prev_v = 0;

        for (int v : diffs) {
            long count = countSubsequencesWithMinDiff(nums, k, v);
            long term = ((long)(v - prev_v) * count) % MOD;
            totalSum = (totalSum + term) % MOD;
            prev_v = v;
        }

        return (int) totalSum;
    }

    private long countSubsequencesWithMinDiff(int[] nums, int k, int minDiff) {
        int n = nums.length;
        long[][] dp = new long[n + 1][k + 1];
        long[][] prefixSum = new long[n + 1][k + 1];

        for (int i = 1; i <= n; i++) {
            dp[i][1] = 1;
            prefixSum[i][1] = prefixSum[i - 1][1] + dp[i][1];
        }

        for (int j = 2; j <= k; j++) {
            int p_ptr = 1;
            for (int i = 1; i <= n; i++) {
                while (p_ptr < i && nums[i - 1] - nums[p_ptr - 1] >= minDiff) {
                    p_ptr++;
                }
                // p_ptr is now at the first index that doesn't satisfy the condition
                // So we can sum up to p_ptr - 1
                if (p_ptr > 0) {
                    dp[i][j] = prefixSum[p_ptr - 1][j - 1];
                }
            }
            for (int i = 1; i <= n; i++) {
                prefixSum[i][j] = (prefixSum[i - 1][j] + dp[i][j]) % MOD;
            }
        }

        return prefixSum[n][k];
    }
}
```
### Algorithm
1. **Sort the Input Array**: Sort `nums` in non-decreasing order.
2. **Key Identity**: The core of this approach is the identity: `Sum(power(S)) = Sum_{d > 0} (number of subsequences with power >= d)`. A subsequence `S` with `power(S) = p` is counted in the sum for `d=1, 2, ..., p`, contributing exactly `p` to the total sum.
3. **Discretize Differences**: The number of subsequences with power `>= d` only changes when `d` crosses a value equal to `nums[j] - nums[i]`. So, we only need to consider these `O(n^2)` difference values. Let `V` be the sorted list of unique positive differences `nums[j] - nums[i]`.
4. **Rewrite Sum**: The total sum can be expressed as `Sum_{i=1 to m} (v_i - v_{i-1}) * N(>=v_i)`, where `v_i` are the unique sorted differences from `V`, `v_0 = 0`, and `N(>=v_i)` is the number of subsequences of length `k` with power at least `v_i`.
5. **DP for N(>=v)**: For a fixed difference `v`, we can calculate `N(>=v)` using dynamic programming in `O(n*k)` time.
   - Let `dp[i][j]` be the number of subsequences of length `j` from `nums[0...i-1]` ending with `nums[i-1]` and having a minimum difference of at least `v`.
   - The transition is `dp[i][j] = sum(dp[p][j-1])` for all `p < i` such that `nums[i-1] - nums[p-1] >= v`.
   - This summation can be optimized. Let `S[i][j]` be the prefix sum `sum_{l=1 to i} dp[l][j]`. Then `dp[i][j] = S[m][j-1]`, where `m` is the largest index such that `nums[m-1] <= nums[i-1] - v`. The index `m` can be found efficiently using a two-pointer technique across the `i` loop.
6. **Main Loop**: Iterate through the sorted unique differences `v` from `V`. In each iteration, calculate `N(>=v)` using the `O(n*k)` DP. Then add `(v - prev_v) * N(>=v)` to the total sum. Update `prev_v = v` and continue. Remember to use modulo arithmetic.

# Solutions
### Java

```java
class Solution {
private
  Map<Long, Integer> f = new HashMap<>();
private
  final int mod = (int)1 e9 + 7;
private
  int[] nums;
public
  int sumOfPowers(int[] nums, int k) {
    Arrays.sort(nums);
    this.nums = nums;
    return dfs(0, nums.length, k, Integer.MAX_VALUE);
  }
private
  int dfs(int i, int j, int k, int mi) {
    if (i >= nums.length) {
      return k == 0 ? mi : 0;
    }
    long key = (1L * mi) << 18 | (i << 12) | (j << 6) | k;
    if (f.containsKey(key)) {
      return f.get(key);
    }
    int ans = dfs(i + 1, j, k, mi);
    if (j == nums.length) {
      ans += dfs(i + 1, i, k - 1, mi);
    } else {
      ans += dfs(i + 1, i, k - 1, Math.min(mi, nums[i] - nums[j]));
    }
    ans %= mod;
    f.put(key, ans);
    return ans;
  }
}

```

### Python

```python
class Solution:
    def sumOfPowers(self, nums: List[int], k: int) -> int: @ cache def dfs(i: int, j: int, k: int, mi: int) -> int: if i >= n: return mi if k == 0 else 0 ans = dfs(i + 1, j, k, mi) if j == n: ans += dfs(i + 1, i, k - 1, mi) else: ans += dfs(i + 1, i, k - 1, min(mi, nums[i] - nums[j])) ans %= mod return ans mod = 10 ** 9 + 7 n = len(nums) nums . sort() return dfs(0, n, k, inf)

```

### CPP

```cpp
class Solution {
public:
  int sumOfPowers(vector<int> &nums, int k) {
    unordered_map<long long, int> f;
    const int mod = 1e9 + 7;
    int n = nums.size();
    sort(nums.begin(), nums.end());
    function<int(int, int, int, int)> dfs = [&](int i, int j, int k, int mi) {
      if (i >= n) {
        return k == 0 ? mi : 0;
      }
      long long key = (1LL * mi) << 18 | (i << 12) | (j << 6) | k;
      if (f.contains(key)) {
        return f[key];
      }
      long long ans = dfs(i + 1, j, k, mi);
      if (j == n) {
        ans += dfs(i + 1, i, k - 1, mi);
      } else {
        ans += dfs(i + 1, i, k - 1, min(mi, nums[i] - nums[j]));
      }
      ans %= mod;
      f[key] = ans;
      return f[key];
    };
    return dfs(0, n, k, INT_MAX);
  }
};

```