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 _thesum of powers of all subsequences of _nums which have length equal to k.

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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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] <= 10^8
  • 2 <= k <= n

Solution

Method 1 – Dynamic Programming with Sorted Array

Intuition

For each subsequence of length k, its power is the minimum absolute difference between any two elements. If we sort the array, the minimum difference in a k-length subsequence is always between two adjacent elements. We can use dynamic programming to count the number of ways to pick k elements and keep track of the minimum difference.

Approach

  1. Sort nums in ascending order.
  2. Use DP: dp[i][j] = sum of powers for picking j elements from the first i elements.
  3. For each i, j:
    • If j == 1, the power is infinity (or a large value, as only one element).
    • For j > 1, the power is the minimum of the previous power and the difference between nums[i-1] and nums[i-2].
  4. For all combinations, sum the powers for all subsequences of length k.
  5. Return the sum modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int sumOfPowers(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1));
        for (int i = 0; i < n; ++i) dp[i][1] = 1;
        for (int j = 2; j <= k; ++j) {
            for (int i = j - 1; i < n; ++i) {
                for (int p = j - 2; p < i; ++p) {
                    int diff = nums[i] - nums[p];
                    dp[i][j] = (dp[i][j] + dp[p][j - 1] * diff) % MOD;
                }
            }
        }
        long long ans = 0;
        for (int i = k - 1; i < n; ++i) ans = (ans + dp[i][k]) % MOD;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func sumOfPowers(nums []int, k int) int {
    const mod = 1_000_000_007
    n := len(nums)
    sort.Ints(nums)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
    }
    for i := 0; i < n; i++ {
        dp[i][1] = 1
    }
    for j := 2; j <= k; j++ {
        for i := j - 1; i < n; i++ {
            for p := j - 2; p < i; p++ {
                diff := nums[i] - nums[p]
                dp[i][j] = (dp[i][j] + dp[p][j-1]*diff%mod) % mod
            }
        }
    }
    ans := 0
    for i := k - 1; i < n; i++ {
        ans = (ans + dp[i][k]) % mod
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int sumOfPowers(int[] nums, int k) {
        int MOD = 1_000_000_7;
        int n = nums.length;
        Arrays.sort(nums);
        long[][] dp = new long[n + 1][k + 1];
        for (int i = 0; i < n; ++i) dp[i][1] = 1;
        for (int j = 2; j <= k; ++j) {
            for (int i = j - 1; i < n; ++i) {
                for (int p = j - 2; p < i; ++p) {
                    int diff = nums[i] - nums[p];
                    dp[i][j] = (dp[i][j] + dp[p][j - 1] * diff) % MOD;
                }
            }
        }
        long ans = 0;
        for (int i = k - 1; i < n; ++i) ans = (ans + dp[i][k]) % MOD;
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun sumOfPowers(nums: IntArray, k: Int): Int {
        val MOD = 1_000_000_7
        val n = nums.size
        nums.sort()
        val dp = Array(n + 1) { LongArray(k + 1) }
        for (i in 0 until n) dp[i][1] = 1L
        for (j in 2..k) {
            for (i in j - 1 until n) {
                for (p in j - 2 until i) {
                    val diff = nums[i] - nums[p]
                    dp[i][j] = (dp[i][j] + dp[p][j - 1] * diff) % MOD
                }
            }
        }
        var ans = 0L
        for (i in k - 1 until n) ans = (ans + dp[i][k]) % MOD
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def sumOfPowers(self, nums: list[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        nums.sort()
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        for i in range(n):
            dp[i][1] = 1
        for j in range(2, k + 1):
            for i in range(j - 1, n):
                for p in range(j - 2, i):
                    diff = nums[i] - nums[p]
                    dp[i][j] = (dp[i][j] + dp[p][j - 1] * diff) % MOD
        ans = 0
        for i in range(k - 1, n):
            ans = (ans + dp[i][k]) % MOD
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn sum_of_powers(nums: Vec<i32>, k: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = nums.len();
        let k = k as usize;
        let mut nums = nums;
        nums.sort();
        let mut dp = vec![vec![0i64; k + 1]; n + 1];
        for i in 0..n { dp[i][1] = 1; }
        for j in 2..=k {
            for i in j - 1..n {
                for p in j - 2..i {
                    let diff = (nums[i] - nums[p]) as i64;
                    dp[i][j] = (dp[i][j] + dp[p][j - 1] * diff) % MOD;
                }
            }
        }
        let mut ans = 0i64;
        for i in k - 1..n {
            ans = (ans + dp[i][k]) % MOD;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    sumOfPowers(nums: number[], k: number): number {
        const MOD = 1e9 + 7;
        const n = nums.length;
        nums.sort((a, b) => a - b);
        const dp: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
        for (let i = 0; i < n; ++i) dp[i][1] = 1;
        for (let j = 2; j <= k; ++j) {
            for (let i = j - 1; i < n; ++i) {
                for (let p = j - 2; p < i; ++p) {
                    const diff = nums[i] - nums[p];
                    dp[i][j] = (dp[i][j] + dp[p][j - 1] * diff) % MOD;
                }
            }
        }
        let ans = 0;
        for (let i = k - 1; i < n; ++i) ans = (ans + dp[i][k]) % MOD;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3) — Three nested loops for DP.
  • 🧺 Space complexity: O(n^2) — For the DP table.