Find the sum of subsequence powers

Array Dynamic Programming Sorting

25.1% acceptance

Feb 25, 2026

148

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 10^9 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn sum_of_powers(nums: Vec<i32>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut nums = nums;
    nums.sort();
    let n = nums.len();
    let k = k as usize;
    // dp[i][j][d] = sum over subsequences ending at index i, having j elements, with min_diff = d
    // But d can be large. Use HashMap for d dimension.
    use std::collections::HashMap;
    // dp[last_idx][count] -> map from min_diff to count_of_subsequences
    let mut dp: Vec<Vec<HashMap<i32, i64>>> = vec![vec![HashMap::new(); k + 1]; n];
    let mut ans = 0i64;
    for i in 0..n {
      dp[i][1].insert(i32::MAX, 1);
      for prev in 0..i {
        let diff = nums[i] - nums[prev];
        for cnt in 1..k {
          let prev_map = dp[prev][cnt].clone();
          for (&min_d, &cnt_v) in &prev_map {
            let new_min = min_d.min(diff);
            *dp[i][cnt+1].entry(new_min).or_insert(0) = (dp[i][cnt+1].get(&new_min).copied().unwrap_or(0) + cnt_v) % MOD;
          }
        }
      }
      // Collect results for cnt == k
      for (&min_d, &cnt_v) in &dp[i][k] {
        ans = (ans + min_d as i64 * cnt_v) % MOD;
      }
    }
    ans as i32
  }
}