Python Bottom-up DP with Combinatorial Optimization O(nk)
IntuitionThe problem requires finding the sum of all possible combinations where we select k elements from the array and take either their minimum or maximum va
# Intuition
The problem requires finding the sum of all possible combinations where we select k elements from the array and take either their minimum or maximum value. By sorting the array first, we can determine that for any k elements:
 * The minimum value will always be the leftmost element of the selected group
 * The maximum value will always be the rightmost element of the selected group
# Approach
1. Sort the array to ensure elements are in ascending order
2. Use dynamic programming to pre-calculate combinations (C(n,r)) for efficiency
3. For each number in the array:
  * When it's the minimum: multiply it by C(i,j-1) as we need to select j-1 more elements from the i elements to its right
  * When it's the maximum: multiply it by C(n-i-1,j-1) as we need to select j-1 more elements from the n-i-1 elements to its left
4. Use modulo arithmetic throughout to prevent overflow
5. The final sum gives us the total of all possible minimum and maximum values
# Complexity
* Time complexity: $$O(nk)$$
  * Building the combinations DP table: O(nk)
  * Main calculation loop: O(nk)
  * Overall complexity is dominated by these two O(nk) operations
* Space complexity: $$O(nk)$$
  * The combinations DP table requires an n×k matrix
  * All other variables use O(1) space
  * The sorted array is modified in-place, so it doesn't contribute additional space

# Code
```python3 []
class Solution:
    MOD = 10 ** 9 + 7
    def minMaxSums(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        total = 0
        
        # Pre-calculate combinations table
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        # Base cases
        for i in range(n + 1):
            dp[i][0] = 1
        for i in range(1, n + 1):
            for j in range(1, min(i + 1, k + 1)):
                dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % self.MOD
        
        # Calculate sum using pre-computed combinations
        for i in range(n):
            for j in range(1, k + 1):
                total = (total + nums[i] * dp[i][j-1]) % self.MOD
                total = (total + nums[i] * dp[n-i-1][j-1]) % self.MOD
                
        return total
                

            
```
['Dynamic Programming', 'Sorting', 'Python3']