#include "partition.h"
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
using ll = long long;

const int MAX_N = 20;
int n;
ll total_sum;
ll lim;
int A[MAX_N];
int min_dif;
std::vector<int> sol;

std::vector<int> positions;
void bkt(int pos, ll sum, int max_val) {
    if(pos >= n) {
        if(sum >= lim && sum - max_val < lim) {
            int sz = int(positions.size());
            if(abs(2 * sz - n) < min_dif) {
                min_dif = abs(2 * sz - n);
                sol = positions;
            }
        }
    } else {
        bkt(pos + 1, sum, max_val);
        positions.push_back(pos);
        bkt(pos + 1, sum + A[pos], std::max(max_val, A[pos]));
        positions.pop_back();
    }
}

std::vector<int> solve(std::vector<int> a) {
    n = int(a.size());
    for(int i = 0; i < n; i++) {
        A[i] = a[i];
    }
    total_sum = 0;
    for(int x : a) {
        total_sum += x;
    }
    lim = (total_sum + 1) / 2;
    min_dif = 1e9;
    bkt(0, 0, 0);
    int j = 0;
    int sz = int(sol.size());
    std::vector<int> push;
    for(int i = 0; i < n; i++) {
        while(j < sz && sol[j] < i) {
            j++;
        }
        if(j < sz && sol[j] > i) {
            push.push_back(i);
        }
    }
    std::sort(sol.begin(), sol.end(), [&](int a, int b) {
        return A[a] < A[b];
    });
    for(int x : push) {
        sol.push_back(x);
    }
    return sol;
}
