#include<bits/stdc++.h>
#include "partition.h"

using namespace std;

vector<int> A;
int S = 0;
int n;
vector<int> eu, sol;
int mini = 0;

void bkt(int it, int suma){
    if(suma * 2 > S){
        if( abs((int)eu.size() - (n - (int)eu.size())) < mini){
            mini = abs((int)eu.size() - (n - (int)eu.size()));
            int j = 0;
            sol = eu;
            for(int i = 0; i < n; i++){
                if(j < eu.size() && eu[j] == i){ j++; continue; }
                sol.push_back(i);
            }
        }
        return;
    }
    if(it == n) return;

    bkt(it + 1, suma);

    eu.push_back(it);
    bkt(it + 1, suma + A[it]);
    eu.pop_back();
}

vector<int> solve(vector<int> a){
    n = a.size();

    if(n == 1) return {0};
    A = a;
    mini = n + 1;
    for(int i = 0; i < n; i++) S += A[i];

    // osa pp ca solutia are fix (n+1)/2 elem
    // acuma trebe doar sa aleg acel subset de elemente a.i. sa dea suma finala > S/2
    // hai sa fac n <= 20

    bkt(0, 0);
    return sol;
}
