a64_q4_clostest_subset.cpp

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<int> a;
vector<int> ps;
int minD = 1e9;
void ncm(int l, int c, int s);
int heuristic();

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    std::cin >> n >> m >> k;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i]; 
    }
    std::sort(a.rbegin(), a.rend()); //max to min to build much first
    ps.resize(n);
    ps[0] = a[0];
    for (int i = 0; i < n; i++) {
        ps[i] = ps[i-1] + a[i];
    }

    ncm(0, 0, 0);

    std::cout << minD << '\n';
    return 0;
}

void ncm(int len, int chosen, int sum) {
    if (len == n) {
        minD = min(minD, abs(sum - k));
        return;
    }
    
    if (sum + (ps[n-1] - ps[n-(m-chosen)-1]) - k > minD) return; //backtracking when too much
    if (k - (sum + (ps[len+(m-chosen)-1] - ps[len-1])) > minD) return; //backtracking too less

    if (chosen < m) {
        ncm(len+1, chosen+1, sum + a[len]);
    }
    if (len - chosen < n - m) {
        ncm(len+1, chosen, sum);
    }
}

int heuristic() {
    return 0;
}