Combinatorics - Count # of ways nums[i] can be used as min and max
Intuition / ApproachWe are asked to count the min and max values of all subsequences of length <= k. A naive approach would be to sort the array (since order on
# Intuition / Approach
We are asked to count the min and max values of all subsequences of length <= k. A naive approach would be to sort the array (since order on subsequences does not matter), generate all subsequences, and count min/max values on all subsequences that have a length <= k. This wont work since $$1 <= n <= 10^5 $$ and generating all subsequences will take $$O(2^n)$$ time.

If we look at the constraints, we can see that $$1 <= k <= min(70,n)$$. This means we might be able to brute force over k.

As mentioned before, we can sort which will cost us $$O(nlogn)$$ time, however this will let us count the contribution of every element.

If we have an $$i$$ loop that iterates over every number in nums, then have an inner $$j$$ loop iterating from $$[1,k]$$, we can use nCr to count the number of ways $$nums[i]$$ can be used as our maximum (number of $$j$$ size subsequences we can form from $$[0,i]$$) as well as the number of ways $$nums[i]$$ can be used as our minimum (number of $$j$$ size subsequences from $$[i,n]$$). Remember that since j is iterating from $$[1,k]$$, we will count all possible subsequences with length $$<= k$$ as the problems requires.

One thing to note is that using standard math.comb() will TLE, so we must precomptue all possible nCr, so that future lookups will be $$O(1)$$.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$\quad \quad O(max(nlogn,n*k))$$

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$\quad \quad O(n*k)$$

# Code
```python3 []
class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        # Set res to account for k == 1 case
        res = 2 * sum(nums)

        nums.sort()
        MOD = 10**9 + 7
        n = len(nums)

        # Precompute nCr for all valid values of n and k
        comb = [[0 for _ in range(k+1)] for _ in range(n+1)]
        comb[0][0] = 1
        for i in range(1, n+1):
            for j in range(min(k+1, i+1)):
                comb[i][j] = comb[i-1][j]
                if j > 0:
                    comb[i][j] += comb[i-1][j-1]
                    comb[i][j] %= MOD

        # Count how many subsequences can use nums[i] as min and how many can use nums[i] as max.
        for i in range(len(nums)):
            for j in range(2,k + 1):
                res += (nums[i]) * comb[i][j - 1]
                res += (nums[i]) * comb[len(nums) - i - 1][j - 1]
                res %= MOD
        return res
```
['Python3']