Efficient Calculation of Weighted Minimum and Maximum Sums from Subsets
IntuitionTo solve this problem, the idea is to calculate two sums: the minimum sum and the maximum sum based on combinations of elements in the array. The minim
# Intuition
To solve this problem, the idea is to calculate two sums: the minimum sum and the maximum sum based on combinations of elements in the array. The minimum sum is derived by taking the smallest numbers weighted by their contribution, and the maximum sum is derived by considering the largest numbers similarly. Since directly calculating combinations every time is inefficient, precomputing the binomial coefficients using Pascal's Triangle ensures an optimal solution.
# Approach
<!-- Describe your approach to solving the problem. -->
Precompute Contributions:
Using dynamic programming (similar to Pascal's Triangle), precompute the contribution count for each possible size of a subset (k). This avoids repetitive calculations during the main iteration.

Sort the Array:
Sorting helps systematically calculate the contributions of the smallest elements to the minimum sum and the largest elements to the maximum sum.

Calculate Minimum Weighted Sum:

For each element, determine its contribution to subsets where it acts as a "minimum" value.
This is done by using the precomputed contribution counts for subsets formed with the remaining elements in the array.
Calculate Maximum Weighted Sum:

Similarly, for each element, determine its contribution to subsets where it acts as a "maximum" value.
Use the same precomputed contribution counts.
Modulo Operation:
Since the result can grow large, every calculation is performed modulo 10**9 +7 to keep numbers manageable.



# Complexity
### Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Precomputing contributions: O(n⋅k).
- Sorting the array: O(nlogn).
- Iterating through the array to compute sums: O(n⋅k).
- Total: O(n⋅k+nlogn).
### Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
- Storing contributions: O(n.k)
- Additional variables: O(1)
- Total: O(n.k)

# Code
```python3 []
class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        MOD = 1000000007
        
        # Precompute contributions for subset sizes
        def precompute_contributions(n, k):
            dp = [[0] * (k + 1) for _ in range(n + 1)]
            for i in range(n + 1):
                dp[i][0] = 1  # Base case: 1 way to pick 0 elements
                for j in range(1, min(i, k) + 1):
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD
            return dp

        # Precompute contributions up to len(nums) and k
        contributions = precompute_contributions(len(nums), k)
        
        # Sort the array
        nums.sort()
        n = len(nums)
        ans = 0

        # Calculate minimum weighted sum
        for i in range(n):
            for j in range(k):
                ans = (ans + nums[i] * contributions[n - i - 1][j]) % MOD
        
        # Calculate maximum weighted sum
        for i in range(n - 1, -1, -1):
            for j in range(k):
                ans = (ans + nums[i] * contributions[i][j]) % MOD
        
        return ans
     
    
```
['Python3']