O(n*k) combination + precomputed factorials. Explained.
IntuitionFirst, sort the numbers. This makes creating combinations easier.Try listing out all the combinations for each size, and look for a pattern.Using nums
# Intuition
First, sort the numbers. This makes creating combinations easier. 

Try listing out all the combinations for each size, and look for a pattern.

Using `nums = [1, 2, 3, 4, 5]` as an example.

For size 3:

`1` appears 6 times in min. This is 4C2 because we choose two numbers from all the numbers that come after 1. There are 6 combinations of those numbers `2 3, 2 4, 2 5, 3 4, 3 5, 4 5`.

`5` appears 6 times in max. This is 4C2 because we choose two numbers from all the numbers that come before 5. There are 6 combinations of those numbers `1 2, 1 3, 1 4, 2 3, 2 4, 3 4`.

| min | |  max |
| -| - | - |
| 1 | 2 | 3 |
| 1 | 2 | 4 |
| 1 | 2 | 5 |
| 1 | 3 | 4 |
| 1 | 3 | 5 |
| 1 | 4 | 5 |
| 2 | 3 | 4 |
| 2 | 3 | 5 |
| 2 | 4 | 5 |
| 3 | 4 | 5 |

Now generalize this pattern into a formula and run it for each index `i [0..n-1]` and `size [1..k]`.

# Approach
- Precompute factorials and inverse factorials.
- `nCr (n choose r) = n! / (n-r)! / r!`.
- For each num at index i, count how many times the num contributes to both min and max.
- It contributes `nCr(n - i - 1, size - 1)` times to min.
- It contributes `nCr(i, size - 1)` times to max.

# Complexity
- Time complexity: `O(n * k)`
- Space complexity: `O(n)`

# Code
Sadly, python solution gives TLE despite having an acceptable time complexity. Used this tool to convert my python solution to C++. https://www.codeconvert.ai/python-to-c++-converter

```python3 []
class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        MOD = 10**9 + 7

        factorial = [1] * (n + 1)
        for i in range(1, n + 1):
            factorial[i] = factorial[i - 1] * i % MOD
        invFactorial = [1] * (n + 1)
        invFactorial[-1] = pow(factorial[-1], -1, MOD)
        for i in reversed(range(1, n)):
            invFactorial[i] = invFactorial[i + 1] * (i + 1) % MOD

        def nCr(n, r):
            res = factorial[n] * invFactorial[n - r] * invFactorial[r] % MOD if n >= r else 0
            return res

        res = 0
        for size in range(1, k + 1):
            for i in range(n):
                minContrib = nCr(n - i - 1, size - 1) * nums[i] % MOD
                maxContrib = nCr(i, size - 1) * nums[i] % MOD
                res = (res + maxContrib + minContrib) % MOD
        return res
```

```cpp []
#include <vector>
#include <algorithm>
#include <iostream>

class Solution {
public:
    int minMaxSums(std::vector<int>& nums, int k) {
        std::sort(nums.begin(), nums.end());
        int n = nums.size();
        const int MOD = 1e9 + 7;

        std::vector<long long> factorial(n + 1, 1);
        std::vector<long long> invFactorial(n + 1, 1);
        for (int i = 1; i <= n; ++i) {
            factorial[i] = factorial[i - 1] * i % MOD;
            invFactorial[i] = pow(factorial[i], MOD - 2, MOD);
        }

        auto nCr = [&](int n, int r) {
            return (n >= r) ? (factorial[n] * invFactorial[n - r] % MOD * invFactorial[r] % MOD) : 0;
        };

        long long res = 0;
        for (int size = 1; size <= k; ++size) {
            for (int i = 0; i < n; ++i) {
                long long minContrib = nCr(n - i - 1, size - 1) * nums[i] % MOD;
                long long maxContrib = nCr(i, size - 1) * nums[i] % MOD;
                res = (res + maxContrib + minContrib) % MOD;
            }
        }
        return res;
    }

private:
    long long pow(long long base, long long exp, long long mod) {
        long long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = result * base % mod;
            }
            base = base * base % mod;
            exp /= 2;
        }
        return result;
    }
};


```
['C++', 'Python3']