C++ Combinatorics: Greater/Smaller than nums[i]
Complexity

Time complexity: O(n∗k+n∗log(n))


Space complexity: O(n)

Code
![image.png](https://assets.leetcode.com/users/images/4ca1fdc5-e827-4670-b716-045fe18817f4_1737260109.7351584.png)

# Complexity
- Time complexity: $O(n*k+n*log(n))$

- Space complexity: $O(n)$

# Code
```cpp []
#include <bits/stdc++.h>
using namespace std;


inline long long mod_exp(long long base, long long exp, long long modd) { unsigned long long ans = 1; base %= modd; while(exp > 0) { if(exp%2==1) ans = (base*ans)%modd; exp /= 2; base = (base*base)%modd; } return ans; }
const long long FMOD = 1e9 + 7;
vector<long long> factorial {1,1}, invfactorial {1,1};

long long calcFactorial(long long n) {
    for(long long i = factorial.size(); i <= n; i++) {
        factorial.push_back(i * factorial[i - 1]);
    }
    return factorial[n];
}
long long modfactorial(long long n) {
    for(long long i = factorial.size(); i <= n; i++) {
        factorial.push_back((i * factorial[i - 1]) % FMOD);
        invfactorial.push_back((mod_exp(i, FMOD-2, FMOD) * invfactorial[i - 1]) % FMOD);
    }
    return factorial[n];
}
const long long MAXFACTORIALN = 100'001;
// auto precomputeFactorial = []() { calcFactorial(MAXFACTORIALN); return true; }();
auto precomputeModFactorial = []() { modfactorial(MAXFACTORIALN); return true; }();

long long nCkMod(int N, int K) {
	if(K > N) return 0LL;
    return factorial[N] * invfactorial[K] % FMOD * invfactorial[N-K] % FMOD;
}

const long long MOD = 1e9 + 7;
class Solution {
public:
    int minMaxSums(vector<int>& nums, int k) {
  		if(k == 1) return (2LL * accumulate(nums.begin(), nums.end(), 0LL)) % MOD;
  		int n = nums.size();
  		map<int, long long> vals;
  		for(int i = 0; i < n; i++) {
  			vals[nums[i]]++;
  		}
  		map<int, long long> pre(vals.begin(), vals.end());
  		for(auto it = next(pre.begin()); it != pre.end(); it++) {
  			it->second += prev(it)->second;
  		}

  		long long ans = 0;
  		for(auto it = pre.begin(); it != pre.end(); it++) {
  			int cntSmaller = (it == pre.begin()) ? 0 : prev(it)->second;
  			int cntGreater = n - it->second;
  			int cntThis = n - cntSmaller - cntGreater;

  			long long bWays = 0, aWays = 0;
  			for(int useThis = k; useThis >= 1; useThis--) {
  				if((k - useThis) >= 0) {
  					if((k - useThis) <= cntSmaller)
  						bWays = (bWays + nCkMod(cntSmaller, k - useThis)) % MOD;
  					if((k - useThis) <= cntGreater)
  						aWays = (aWays + nCkMod(cntGreater, k - useThis)) % MOD;
  				}
  				if(useThis <= cntThis) {
  					// w = choose "useThis" elements from "cntThis" elements
  					// pairing with below: contributing as max element, pairing with up: contributing as min element
  					long long w = nCkMod(cntThis, useThis) % MOD;
	  				ans += w * bWays % MOD * it->first % MOD;
	  				ans += w * aWays % MOD * it->first % MOD;
	  				ans %= MOD;
  				}
  			}
  		}
  		return ans % MOD;
    }
};
```
['Combinatorics', 'C++']