Optimal Solution with proof. O(nlog(n))
ApproachSort the array. Now we can find the contribution of each element when it is the maximum and minimum respectively.
Let's consider the contribution of an
# Approach
Sort the array. Now we can find the contribution of each element when it is the maximum and minimum respectively.
Let's consider the contribution of an element when it's the maximum.
Contribution ($$C_{i}$$) for an element at index i would be nums[i] multipied by the number of subsequences having length at most k and ending at index i. Therefore,
$$ C_{i} = (\sum_{j = 0}^{k - 1}\binom{i}{j}) * nums[i]$$
Thus the total sum can be calculated by summing up the contribution of each index in $$O(nk)$$ time by precalculating the factorial values.

However, the formula can be reduced further as follows. Let 
$$S_{i + 1} = \sum_{j = 0}^{k - 1}\binom{i + 1}{j}$$
$$= \binom{i + 1}{0} + \binom{i + 1}{1} + \binom{i + 1}{2} + \cdots + \binom{i + 1}{k - 2} + \binom{i + 1}{k - 1}$$
$$=\binom{i}{0} + [\binom{i}{0} + \binom{i}{1}] + [\binom{i}{1} + \binom{i}{2}] + \cdots  + [\binom{i}{k - 3} + \binom{i}{k - 2}] + [\binom{i}{k - 2} + \binom{i}{k - 1}]$$    ($$\because \binom{i + 1}{j} = \binom{i}{j - 1} + \binom{i}{j}$$)

$$= 2S_{i} - \binom{i}{k - 1}$$

This recursive formula helps us to calculate the total sum in  $$O(n)$$ (after sorting)
Note: The same value of $$S_{i}$$ is used for contribution of nums[i] as maximum and contribution of nums[n - 1 - i] as minimum.

# Complexity
- Time complexity: $$O(nlog(n))$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(1)$$ per test case.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
#define ll long long
const ll mod = 1e9 + 7;
const ll MAX = 100001;
vector<ll> factInverse(MAX + 1);
vector<ll> inverse(MAX + 1);
vector<ll> fact(MAX + 1);

void calcInverse()
{
    inverse[0] = inverse[1] = 1;
    for (ll i = 2; i <= MAX; i++)
        inverse[i] = (inverse[mod % i] * (mod - mod / i)) % mod;
}

void calcFactInverse()
{
    factInverse[0] = factInverse[1] = 1;
    for (ll i = 2; i <= MAX; i++)
        factInverse[i] = (inverse[i] * factInverse[i - 1]) % mod;
}

void calcFactorial()
{
    fact[0] = 1;
    for (ll i = 1; i <= MAX; i++)
        fact[i] = (fact[i - 1] * i) % mod;
}

ll C(ll n, ll R)
{
    if (n < R || R < 0 || n < 0)
        return 0;
    ll ans = (((fact[n] * factInverse[R]) % mod) * factInverse[n - R]) % mod;
    return ans;
}

class Solution {
public:
    void init() {
        if (inverse[0] == 0) {
            calcInverse();
            calcFactInverse();
            calcFactorial();
        }
    }
    int minMaxSums(vector<int>& nums, int k) {
        init();
        int n = nums.size();
        sort(nums.begin(), nums.end());
        ll ans = 0, sum = 1;
        for (int i = 0; i < n; i++) {
            ans = (ans + (sum * ((nums[i] + nums[n - 1 - i]) % mod)) % mod) % mod;
            sum = (((2LL * sum) % mod) - C(i, k - 1) + mod) % mod;
        }
        return (int)ans;
    }
};
```
['C++']