Python3 | Detailed explanation Combinatorics
IntuitionSort the list, get pointers to both sides (min, and max), and then for each size k calculate how many subsequences you can create of size k that these
# Intuition
Sort the list, get pointers to both sides (min, and max), and then for each size k calculate how many subsequences you can create of size k that these pointers will be present. Keep iterating both pointers towards the center of the list. 

# Approach

Lets walk through an example of a sorted list `[   1, 2, 3, 4, 5, 6, 7, 8   ]`, and k = 3:

1. start min and max pointers
```
 _min                    _max
[   1, 2, 3, 4, 5, 6, 7, 8   ]
k = 3
```

2. calculate how many groups of size 3 we can create.

for our pointers _min and _max, let's try to calculate how many subsequences where _min and _max are _actually_ the min and max elements, such that subsequence will have the form:
```
[1, X, Y]
[X, Y, 8]
```

**For [1, X, Y]:**
Since element 1 is already in the subsequence, we want to find how many ways we can fill X and Y. That's comb(7, 2). comb(7, 2) = if you have 7 elements ([ 2, 3, 4, 5, 6, 7, 8], notice how this list contains all elements except 1, as its already in the subsequence), in how many ways can we choose a group of 2 values?

> '7' here is what's referred to as possibles_right on the code

> '2' comes from k - 1. Where k for this example is equals to 3.

The formula for comb function:
![image.png](https://assets.leetcode.com/users/images/81494686-a0e6-40e1-a10a-ff4fbb28396e_1737282402.1815896.png)

This gives us the answer to the question of how many subsequences we'll get where 1 is the minimum element.

```
>>> import math
>>> math.comb(7, 2)
21
```

Notice how the above (comb(7, 2)) is the same for [X, Y, 8] due to the _min and _max pointers mirrorring each other position's in the original list. So there are 21 ways in which 1 is the minimum value and 8 is the maximum value. Meaning that we can aggregate those into our response:

```
res += (1 + 8) * 21
```

Once this loop is done for _min and _max pointer, iterate both towards the center of the array:
```
    _min               _max
[ 1,    2, 3, 4, 5, 6,    7, 8]
```

Lets move it one more iteration to show the next relevant property:
```
        _min        _max
[ 1, 2,    3, 4, 5,    6, 7, 8]
```

Now besides the original formula as described above to find the number of subsequences where _min is the minimum element and _max is the max element:
```
# [3, X, Y]
# [X, Y, 6]
```

We'll also need to find the number of subsequences where _min is the max element, and _max is the min element, see:
```
# [X, Y, 3]
# [6, X, Y]
```

Now we need to know how many numbers are below the _min pointer (this is the *same as* how many numbers are above the _max pointer). The list of numbers lower than the _min pointer is `[1, 2]`, so we'll compute comb(2, 2)

> the first '2' on comb(2, 2) comes from the size of the list. This is also referred to as possibles_left on the code

> the second '2' on comb(2, 2) comes from k - 1.

> notice how this follows the same properties from the earlier example

That's it!

## Implementation Details

You can remove a good chunk of the code and use python math lib:
```
import math
math.comb(a, b)
```

but this gives TLE. So we do some precomputation of factorials and inverse factorials to speed up the process of finding the combination.

> Inverse factorials are required to keep the property of `% MOD` alive, because we'll be always multiplying. Divisions will break the property.


# Code
```python3 []
import math

MOD = 10**9 + 7

class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        res = 0
        size = len(nums)
        nums.sort()

        # precompute factorials to speed up execution
        # math.comb gives TLE
        fact = [1] * (size+1)
        inv_fact = [1] * (size+1)

        for i in range(1, size+1):
            fact[i] = fact[i-1] * i % MOD

        inv_fact[size] = pow(fact[size], MOD-2, MOD)
        for i in reversed(range(size)):
            # the inv_fact is a number that follows:
            # (fact[n] * inv_fact[n]) % MOD = 1
            # can also be expressed as:
            # n! * 1/n! = 1
            inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD

        def comb(x, r):
            # optimized math.comb using precomputed factorials
            if r < 0 or r > x:
                return 0
            return (fact[x] * inv_fact[r]) * inv_fact[x - r]

        for r in range(1, k+1):
            c_nums = deque(nums)
            while c_nums:
                st_size = len(c_nums)
                possibles_right = size - ((size - st_size) // 2) - 1
                possibles_left = size - possibles_right - 1
                
                # left = min, right = max
                # always get at least left element
                min_ = c_nums.popleft()
                # odd sized arrays won't have the last right element
                # so only get right if it exists
                max_ = min_ if not c_nums else c_nums.pop()

                # calculate how many r sized possibilities we have
                # towards the right and left of the array.
                # min_ and max_ positions are mirrored, meaning the
                # numbers of possibilities are the same for both
                # math.comb(a, b) instead of comb(a, b) gives TLE
                res += (min_ + max_) * comb(possibles_right, r - 1)
                res += (min_ + max_) * comb(possibles_left, r - 1) * int(st_size > 1)
        
        return res % MOD
```
['Python3']