# Maximum and Minimum Sums of at Most Size K Subsequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-and-minimum-sums-of-at-most-size-k-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/maximum-and-minimum-sums-of-at-most-size-k-subsequences
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` and a positive integer `k`. Return the sum of the **maximum** and **minimum** elements of all **subsequences** of `nums` with **at most** `k` elements.

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

**Example 1:**

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

**Output:** 24

**Explanation:**

The subsequences of `nums` with at most 2 elements are:

| **Subsequence** | Minimum | Maximum | Sum |
| --------------- | ------- | ------- | --- |
| \[1\]           | 1       | 1       | 2   |
| \[2\]           | 2       | 2       | 4   |
| \[3\]           | 3       | 3       | 6   |
| \[1, 2\]        | 1       | 2       | 3   |
| \[1, 3\]        | 1       | 3       | 4   |
| \[2, 3\]        | 2       | 3       | 5   |
| **Final Total** |         |         | 24  |

The output would be 24.

**Example 2:**

**Input:** nums = \[5,0,6\], k = 1

**Output:** 22

**Explanation:** 

For subsequences with exactly 1 element, the minimum and maximum values are the element itself. Therefore, the total is `5 + 5 + 0 + 0 + 6 + 6 = 22`.

**Example 3:**

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

**Output:** 12

**Explanation:**

The subsequences `[1, 1]` and `[1]` each appear 3 times. For all of them, the minimum and maximum are both 1\. Thus, the total is 12.

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 109`
* `1 <= k <= min(70, nums.length)`

# Approaches
## Brute-Force Generation of Subsequences
This approach involves generating all possible non-empty subsequences of the input array `nums`. For each generated subsequence, we check if its size is at most `k`. If it is, we find its minimum and maximum elements and add their sum to a running total. This is the most straightforward but also the most inefficient way to solve the problem.
**Time:** O(k * 2^n). There are `2^n` subsequences. For each valid one, we iterate up to `k` elements to find the min and max. · **Space:** O(n * 2^n) if storing all subsequences, or O(n) for recursion depth if processing on-the-fly.
**Pros:** Simple to understand and implement.; Correctly solves the problem for very small input sizes.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will cause a Time Limit Exceeded (TLE) error for constraints where `n` is larger than about 20.; May also lead to Memory Limit Exceeded (MLE) if all subsequences are stored.
### Explanation
We can implement this using a recursive helper function. The function explores two choices for each element in `nums`: either include it in the current subsequence or not. This process naturally generates all `2^n` subsequences. Once a subsequence is formed (when the recursion reaches the end of the array), we check if it meets the size criteria (`1 <= size <= k`). If it does, we compute its minimum and maximum values and add them to a global sum. All additions are performed modulo `10^9 + 7`.

```java
class Solution {
    long totalSum = 0;
    int MOD = 1_000_000_007;

    public int maximumMinimumSum(int[] nums, int k) {
        // This conceptual brute-force approach will time out.
        List<List<Integer>> allSubsequences = new ArrayList<>();
        generateSubsequences(nums, 0, new ArrayList<>(), allSubsequences);
        
        for (List<Integer> sub : allSubsequences) {
            if (sub.size() > 0 && sub.size() <= k) {
                long minVal = Long.MAX_VALUE, maxVal = Long.MIN_VALUE;
                for (int val : sub) {
                    minVal = Math.min(minVal, val);
                    maxVal = Math.max(maxVal, val);
                }
                totalSum = (totalSum + minVal + maxVal) % MOD;
            }
        }
        return (int) totalSum;
    }

    private void generateSubsequences(int[] nums, int index, List<Integer> current, List<List<Integer>> allSubsequences) {
        if (index == nums.length) {
            allSubsequences.add(new ArrayList<>(current));
            return;
        }
        // Exclude nums[index]
        generateSubsequences(nums, index + 1, current, allSubsequences);
        // Include nums[index]
        current.add(nums[index]);
        generateSubsequences(nums, index + 1, current, allSubsequences);
        current.remove(current.size() - 1); // Backtrack
    }
}
```
### Algorithm
*   Initialize a global variable `totalSum` to 0.
*   Define a recursive function, say `generate(index, currentSubsequence)`, to generate all subsequences.
*   The base case for the recursion is when `index` reaches the end of the `nums` array.
*   In the base case, if the `currentSubsequence` is not empty, it represents one of the `2^n` possible subsequences. Add it to a list of all subsequences.
*   The recursive step involves two calls:
    1.  One that excludes `nums[index]` from the subsequence: `generate(index + 1, currentSubsequence)`.
    2.  One that includes `nums[index]`: `currentSubsequence.add(nums[index]); generate(index + 1, currentSubsequence);` followed by backtracking.
*   After generating all subsequences, iterate through them.
*   For each subsequence, if its size is greater than 0 and at most `k`, find its minimum and maximum elements.
*   Add the sum of the minimum and maximum to `totalSum`, taking the result modulo `10^9 + 7`.
*   Return the final `totalSum`.

## Combinatorial Counting
Instead of enumerating subsequences, we can change our perspective. For each element `nums[i]`, we count how many valid subsequences have it as a minimum and how many have it as a maximum. To make this counting easier, we first sort the array `nums`. The total sum is the sum of `nums[i] * (count_as_min + count_as_max)` over all `i`.
**Time:** O(n log n + n*k). Sorting takes `O(n log n)`. Precomputation takes `O(n)`. The main loop is `O(n*k)`. · **Space:** O(n) to store precomputed factorials and their modular inverses.
**Pros:** Much more efficient than brute-force.; Correctly handles the problem constraints by using mathematical properties.; The logic is systematic and based on solid combinatorial principles.
**Cons:** The `O(n*k)` complexity might be too slow if both `n` and `k` were large, but it's acceptable for the given constraints.; Can be further optimized to avoid the nested loop.
### Explanation
First, we sort the array `nums`. This allows us to easily identify elements smaller or larger than `nums[i]`. The total sum can be split into `Sum(max(S))` and `Sum(min(S))` over all valid subsequences `S`.

**Sum of Maximums**: For `nums[i]` to be the maximum of a subsequence `S` of size `s` (where `1 <= s <= k`), `S` must contain `nums[i]`, and its other `s-1` elements must be chosen from the `i` elements smaller than it (`nums[0], ..., nums[i-1]`). The number of ways to do this is `C(i, s-1)`. Summing over all possible sizes `s` from 1 to `k`, `nums[i]` is a maximum in `Sum_{j=0 to k-1} C(i, j)` subsequences.

**Sum of Minimums**: Similarly, for `nums[i]` to be the minimum, the other `s-1` elements must be chosen from the `n-1-i` elements larger than it (`nums[i+1], ..., nums[n-1]`). The number of ways is `Sum_{j=0 to k-1} C(n-1-i, j)`.

We can precompute factorials and their modular inverses to calculate `C(n, r)` in `O(1)`. The main loop iterates `n` times, and inside it, we calculate these sums of combinations, each taking `O(k)` time.

```java
import java.util.Arrays;

class Solution {
    int MOD = 1_000_000_007;
    long[] fact;
    long[] invFact;

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

        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = power(fact[i], MOD - 2);
        }

        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            long countMax = 0;
            for (int j = 0; j < k; j++) {
                countMax = (countMax + nCr(i, j)) % MOD;
            }

            long countMin = 0;
            for (int j = 0; j < k; j++) {
                countMin = (countMin + nCr(n - 1 - i, j)) % MOD;
            }

            long term = (long)nums[i] * (countMax + countMin) % MOD;
            totalSum = (totalSum + term) % MOD;
        }

        return (int) totalSum;
    }

    private long nCr(int n, int r) {
        if (r < 0 || r > n) return 0;
        return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
    }

    private long power(long base, int exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
*   Define `MOD = 10^9 + 7`.
*   Sort the input array `nums` in non-decreasing order.
*   Precompute `factorials` and `inverseFactorials` up to `n` modulo `MOD` to calculate binomial coefficients `C(n, r)` efficiently.
*   Initialize `totalSum = 0`.
*   Iterate through the sorted array with index `i` from `0` to `n-1`:
    *   Calculate `countMax`, the number of times `nums[i]` is a maximum. This is `Sum_{j=0 to k-1} C(i, j)`.
    *   Calculate `countMin`, the number of times `nums[i]` is a minimum. This is `Sum_{j=0 to k-1} C(n-1-i, j)`.
    *   The contribution of `nums[i]` to the total sum is `nums[i] * (countMax + countMin)`.
    *   Add this contribution to `totalSum` modulo `MOD`.
*   Return `totalSum`.

## Optimized Combinatorial Approach with Dynamic Programming
This approach builds upon the combinatorial counting method. We can optimize the calculation of the number of times each element acts as a maximum or minimum. By rearranging the summation and finding a recurrence relation, we can reduce the complexity from `O(n*k)` to `O(n)`, making sorting the bottleneck.
**Time:** O(n log n). Sorting takes `O(n log n)`. Precomputing inverses, computing the `T` array, and the final summation all take `O(n)`. · **Space:** O(n) for storing the sorted array, modular inverses, and the DP array `T`.
**Pros:** Highly efficient, with a time complexity dominated by sorting.; Optimal solution for the given constraints.; Demonstrates a deep understanding of combinatorial identities and dynamic programming.
**Cons:** The derivation of the recurrence relation is non-trivial and requires strong combinatorial reasoning.
### Explanation
After sorting `nums`, we found the total sum to be `Sum_{i=0 to n-1} (nums[i] + nums[n-1-i]) * (Sum_{j=0 to k-1} C(i, j))`. Let `T(i) = Sum_{j=0 to k-1} C(i, j)`. The main challenge is to compute `T(i)` for all `i` from `0` to `n-1` efficiently.

We can derive a recurrence for `T(i)` using Pascal's identity `C(n, r) = C(n-1, r) + C(n-1, r-1)`:
`T(i) = Sum_{j=0 to k-1} C(i, j) = Sum_{j=0 to k-1} (C(i-1, j) + C(i-1, j-1))`
`T(i) = Sum_{j=0 to k-1} C(i-1, j) + Sum_{j=0 to k-1} C(i-1, j-1)`
`T(i) = T(i-1) + (T(i-1) - C(i-1, k-1))`
`T(i) = 2 * T(i-1) - C(i-1, k-1)`

With this recurrence, we can compute the entire `T` array in `O(n)` time. We start with `T[0] = 1`. In each step `i`, we calculate `T[i]` using `T[i-1]` and `C(i-1, k-1)`. The term `C(i-1, k-1)` can also be updated in `O(1)` from `C(i-2, k-1)` from the previous step. This makes the entire calculation `O(n)` after the initial sort.

```java
import java.util.Arrays;

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

        Arrays.sort(nums);

        long[] inv = new long[n + 1];
        if (n > 0) inv[1] = 1;
        for (int i = 2; i <= n; i++) {
            inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
        }

        long[] T = new long[n];
        if (n > 0) T[0] = 1; // Sum_{j=0 to k-1} C(0, j) = C(0,0) = 1

        long c_prev = (k == 1) ? 1 : 0; // C(0, k-1)

        for (int i = 1; i < n; i++) {
            // T[i] is based on T[i-1] and C(i-1, k-1) which is c_prev
            T[i] = (2 * T[i - 1] - c_prev + MOD) % MOD;
            
            // Update c_prev to C(i, k-1) for the next iteration
            if (i > k - 1) {
                long c_curr = (c_prev * i) % MOD;
                c_curr = (c_curr * inv[i - (k - 1)]) % MOD;
                c_prev = c_curr;
            } else if (i == k - 1) {
                c_prev = 1;
            } else { // i < k - 1
                c_prev = 0;
            }
        }

        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            long pairSum = (long)nums[i] + nums[n - 1 - i];
            long term = (pairSum * T[i]) % MOD;
            totalSum = (totalSum + term) % MOD;
        }

        return (int) totalSum;
    }
}
```
### Algorithm
*   Define `MOD = 10^9 + 7`.
*   Sort the input array `nums`.
*   Precompute modular inverses up to `n` in `O(n)` time.
*   Let `T(i) = Sum_{j=0 to k-1} C(i, j)`. We can compute `T` values using the recurrence `T(i) = 2 * T(i-1) - C(i-1, k-1)`.
*   Create an array `T` of size `n`.
*   Initialize `T[0] = 1`.
*   Initialize `c_prev = C(0, k-1)`.
*   Loop `i` from `1` to `n-1`:
    *   Calculate `T[i] = (2 * T[i-1] - c_prev + MOD) % MOD`.
    *   Update `c_prev` to `C(i, k-1)` for the next iteration. This update can be done in `O(1)` using the previous value: `C(i, k-1) = C(i-1, k-1) * i * inv[i - k + 1]`.
*   The total sum is `Sum_{i=0 to n-1} (nums[i] + nums[n-1-i]) * T[i]`.
*   Calculate this final sum in an `O(n)` loop, taking modulo at each step.
*   Return the result.