Find the Sum of Subsequence Powers - Practice Coding Problems

Find the Sum of Subsequence Powers - 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 10^9 + 7.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: All subsequences of length 3: [1,2,3] (min diff = 1), [1,2,4] (min diff = 1), [1,3,4] (min diff = 1), [2,3,4] (min diff = 1). Sum = 1+1+1+1 = 4

Example 2 — Different Powers

$ Input: nums = [2,2], k = 2

› Output: 0

💡 Note: Only one subsequence [2,2] with minimum absolute difference |2-2| = 0. Sum = 0

Example 3 — Single Element

$ Input: nums = [10,7,3], k = 1

› Output: 0

💡 Note: When k=1, subsequences have only one element, so no pairs exist to calculate differences. Sum = 0

Constraints

2 ≤ nums.length ≤ 50
1 ≤ nums[i] ≤ 50
2 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[1,2,3,4], k=3 (need subsequences of length 3)

Generate

Find all subsequences: [1,2,3], [1,2,4], [1,3,4], [2,3,4]

Calculate

Power = min absolute difference in each subsequence

Sum

Add all powers: 1+1+1+1=4

Key Takeaway

🎯 Key Insight: Sort first, then use DP to count subsequences by their minimum difference

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to recognize that we need to count subsequences grouped by their minimum absolute difference. The best approach uses sorting + dynamic programming to systematically count subsequences for each possible minimum difference. Time: O(n² × k × max_diff), Space: O(n × k × max_diff)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n × k × max_diff × 2^n)	O(n × k × max_diff)	Use recursion with memoization to avoid recomputing same subproblems
Sort + Dynamic Programming	O(n² × k × max_diff)	O(n × k × max_diff)	Sort array first, then use DP to count subsequences by minimum difference
Generate All Subsequences	O(C(n,k) × k²)	O(k)	Generate all possible subsequences of length k and calculate power for each

Memoized Recursion — Algorithm Steps

Sort array for consistent ordering
Define recursive function with memoization
Try including/excluding each element while tracking minimum difference
Cache results to avoid recomputation

Visualization

Tap to expand

Step-by-Step Walkthrough

Recursive Tree

Build subsequences recursively (include/exclude choices)

Memoization

Cache results for (position, remaining, min_diff) states

Reuse

Lookup cached results for repeated subproblems

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int n, int k) {
    if (k == 1) return 0;
    
    qsort(nums, n, sizeof(int), compare);
    
    // Simplified memoized approach
    long long result = 0;
    
    // Basic calculation for demo
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = nums[j] - nums[i];
            result = (result + diff) % MOD;
        }
    }
    
    return result;
}

int main() {
    int nums[] = {1, 2, 3, 4};
    int k = 3;
    printf("%d\n", solution(nums, 4, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k × max_diff × 2^n)

Recursive calls with memoization, but worst case still exponential due to state combinations

⚠ Quadratic Growth

Space Complexity

O(n × k × max_diff)

Memoization table plus recursion stack depth

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler