Skip to main content
Talentd

Find the Sum of Subsequence Powers - Solution & Explanation

HardArrayDynamic ProgrammingSorting20 min readAsked at: Rubrik
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array and must compute the total power of all valid subsequences. The power of a subsequence depends on the difference between elements after ordering, so you must carefully track element relationships while enumerating subsequences. A naive enumeration quickly becomes infeasible because the number of subsequences grows exponentially.

Approach 1: Dynamic Programming (O(n² * k) time, O(n * k) space)

Start by sorting the array so differences between elements can be processed in increasing order. Sorting allows you to compute the contribution of each pair or group of elements without recomputing gaps repeatedly. Use dynamic programming where dp[i][j] represents the number of ways to form subsequences of length j ending at index i. While extending subsequences, track the minimum difference between elements, which determines the power contribution.

Each new element attempts to extend subsequences that end before it. Iterate over previous indices and update DP states based on the difference between the current value and earlier values. The accumulated contribution of these differences builds the final answer. This method works well because sorting converts the problem into a structured progression of states instead of exploring every subsequence explicitly. It combines ideas from Dynamic Programming and Sorting to avoid exponential enumeration.

Approach 2: Kadane's Algorithm Inspired Optimization (O(n) time, O(1) space)

Some variations of the problem allow reducing the computation by observing that contributions of differences behave similarly to subarray accumulation. After sorting the array, treat the differences between consecutive elements as a sequence and accumulate contributions in a running manner. Similar to Kadane's Algorithm, maintain a running contribution and update the total whenever extending the current subsequence improves the cumulative power.

This approach works when the subsequence constraints allow linear accumulation of contributions. Instead of tracking all DP states, the algorithm maintains a running sum and updates it while scanning the array. The memory footprint drops to constant space, and the runtime becomes linear. The technique borrows the prefix accumulation idea commonly used in Array problems and Kadane-style maximum subarray logic.

Recommended for interviews: The dynamic programming solution is typically what interviewers expect. It demonstrates that you recognize the exponential subsequence space and replace it with structured DP states after sorting the input. Explaining the brute force idea first shows you understand the search space, but implementing the DP transition proves algorithmic maturity and control over time complexity.

Approach 1: Approach 1: Dynamic Programming

This approach leverages dynamic programming to break down the problem into subproblems, solving and combining them to build the solution.

The solution uses a dynamic programming technique to compute the maximum sum subarray. We maintain a dp array where dp[i] stores the maximum sum ending at index i. This helps to avoid recomputation and results in an optimal solution.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Approach 2: Kadane's Algorithm

Kadane's algorithm offers an optimized way to solve the maximum subarray problem using only a constant amount of space.

This C solution uses Kadane's algorithm to efficiently find the maximum sum subarray. It iteratively calculates the current local maximum and updates the global maximum if the local maximum exceeds it.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Memoization Search

Given the problem involves the minimum difference between elements of a subsequence, we might as well sort the array nums, which facilitates the calculation of the minimum difference between subsequence elements.

Next, we design a function dfs(i, j, k, mi), representing the value of the energy sum when processing the i-th element, the last selected element is the j-th element, k more elements need to be selected, and the current minimum difference is mi. Therefore, the answer is dfs(0, n, k, +infty) (If the last selected element is the n-th element, it indicates that no element has been selected before).

The execution process of the function dfs(i, j, k, mi) is as follows:

  • If i geq n, it means all elements have been processed. If k = 0, return mi; otherwise, return 0.
  • If the remaining number of elements n - i is less than k, return 0.
  • Otherwise, we can choose not to select the i-th element, and the energy sum obtained is dfs(i + 1, j, k, mi).
  • We can also choose to select the i-th element. If j = n, it means no element has been selected before, then the energy sum obtained is dfs(i + 1, i, k - 1, mi); otherwise, the energy sum obtained is dfs(i + 1, i, k - 1, min(mi, nums[i] - nums[j])).
  • We add up the above results and return the result modulo 10^9 + 7.

To avoid repeated calculations, we can use memoization, saving the results that have already been calculated.

The time complexity is O(n^4 times k), and the space complexity is O(n^4 times k). Here, n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Dynamic Programming

Time Complexity: O(n)
Space Complexity: O(n)

Approach 2: Kadane's Algorithm

Time Complexity: O(n)
Space Complexity: O(1)

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with SortingO(n² * k)O(n * k)General solution for computing contributions of all subsequences
Kadane-Inspired AccumulationO(n)O(1)When subsequence power can be derived from consecutive differences

Video Solution

3098. Find the Sum of Subsequence Powers | 4D DP | time- O(n^5) [*will be updated for O(n^4)] • Aryan Mittal • 3,462 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Find the Sum of Subsequence Powers easy or hard?
Find the Sum of Subsequence Powers is classified as a Hard problem. The challenge comes from handling exponentially many subsequences and designing a dynamic programming strategy that counts their contributions efficiently.
Find the Sum of Subsequence Powers Python/Java solution
Implement the dynamic programming approach after sorting the input array. Use nested loops to extend subsequences and update DP states based on element differences. The same logic translates easily across Python, Java, C++, C#, and JavaScript implementations.
How to solve Find the Sum of Subsequence Powers in O(n)?
An optimized approach can treat element differences as a running contribution and accumulate them using a Kadane-style scan. By maintaining a running value while iterating through the sorted array, the algorithm updates the total power without storing all DP states. This reduces time to O(n) and space to O(1) when the constraints allow linear accumulation.
What is the best approach for Find the Sum of Subsequence Powers?
The most reliable solution uses sorting combined with dynamic programming. Sorting ensures differences between elements are processed in order, and DP tracks subsequences ending at each index. This avoids enumerating all subsequences and reduces the complexity to roughly O(n² * k) instead of exponential.
Is Find the Sum of Subsequence Powers asked at Google/Amazon/Meta?
Hard dynamic programming and subsequence enumeration problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. They test your ability to reduce exponential subsequence searches into structured DP transitions and reason about combinatorial contributions.
What data structure is used in Find the Sum of Subsequence Powers?
The core solution uses arrays for dynamic programming states along with sorting. The sorted array allows efficient computation of element differences, while DP tables track counts or contributions of subsequences ending at each index.
What is the time complexity of Find the Sum of Subsequence Powers?
The dynamic programming solution typically runs in O(n² * k) time, where n is the number of elements and k is the subsequence length constraint. Space complexity is O(n * k) for storing DP states. Optimized variants can reduce space or computation depending on the constraints.

Ready to solve this problem?

Practice Find the Sum of Subsequence Powers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Closest Subsequence Sum

Next

Number of Subsequences That Satisfy the Given Sum Condition