Python Combinatorics Explained ✅ | O(n log n)
SolutionOptimal DP combinatorics solution.Time complexity:O(nlogn)- since we sort the arraySpace complexity:O(1)ExplanationConsider the following example from t
# Solution

Optimal DP combinatorics solution.

Time complexity: $O(n \log n)$ - since we sort the array
Space complexity: $O(1)$

```python3 []
class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        nums.sort()
        total_sums = 0
        quantity = 1
        
        for i in range(len(nums)):
            total_sums += quantity * (nums[i] + nums[-i - 1])
            quantity = 2 * quantity - comb(i, k - 1)

        return total_sums % (10 ** 9 + 7)
```

# Explanation

Consider the following example from the problem description. Instead of going through all subsequences and computing the sum of all minimum and maximums, the intuition here is to take each number, say 1, and count the `quantity` of combinations in the table where 1 is the minimum. Then the `quantity * number` will be the contribution that number makes to the total sum.


**Input:** `nums = [1,2,3]`, `k = 2`  
**Output:** `24`  


| 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   |

In our example above 1 appears 3 times as the minimum so it has a total contribution of 3 as the minimum. 2 appears twice so it has a total contribution of 4 as the minimum and so on.

We compute the contribution of a given number as follows. First sort the array so we can start with the smallest numbers first. In our example `nums` is already sorted. Consider the number 1, for a subsequence of size 2 we can make $\binom{2}{1}$ subsequences that have 1 as a minimum for a conbtribution of $\binom{2}{1} \cdot 1$. That's because we have two numbers in our array that are larger than 1, hence the two in $\binom{2}{1}$, and we only need 1 more number to make a subsequence of size 2, hence the 1 in $\binom{2}{1}$.

We can generalize this contribution across all numbers and all subsequences sizes to $\sum_{i=1}^n\sum_{s=1}^k \binom{n - i - 1}{s} \cdot \text{nums}_i$. Here $s$ is the size of our subsequence, n is the size of `nums` and $n - i - 1$ are the number of items larger than the current number in our sorted array (it's just the length of the array minus the current index). This formula is the entire solution to this problem, it computes the total contribution of each number for every size but only for the minimum. Flip it and you can compute all contributions for the maximum. However it's a little slow, given it operates in $O(nk)$ time. 

We optimize our solution with dynamic programming, by working backwards. We can only make 1 subsequence with the last number as the minimum and the first number as the maximum, so we start with `quantity = 1` in our code. Then for each subsequent number we double the number of subsequences we can make up until k.

Let's revisit our code now. `total_sums += quantity * (nums[i] + nums[-i - 1])` is adding the contribution made from the maximum and minimum number. Then `quantity = 2 * quantity` is doing this doubling of subsequences with our given number as the min/max but after i exceeds k we have to adjust for the fact that we can't make subsequences longer than k and sutract all subsequences longer than k from the quantity hence the `- comb(i, k - 1)`.

['Math', 'Dynamic Programming', 'Combinatorics', 'Python3']