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

using namespace std;
const int MAXN = 20;

vector<int> rez;
vector<int> v;
int comb[MAXN + 1]; //daca iau indicele i sau nu
int mini, n;

void bkt( int k, int s2 ) {
    int i, sumA, cntA, cntB, diff;
    if( k == n + 1 ) {
        sumA = cntA = cntB = diff = 0;
        vector<int> ind;
        for( i = 0; i < n; i++ )
            if( comb[i] == 1 ) { //prima jumatate
                cntA++;
                sumA += v[i];
                ind.push_back( i );
            }
            else {
                cntB++;
            }
        diff = abs( cntA - cntB );
        if( sumA > s2 && diff < mini )
        {
            for( i = 0; i < n; i++ )
                if( comb[i] == 0 )
                    ind.push_back( i );
            mini = diff;
            rez = ind;
        }
    } else {
        for( i = 0; i <= 1; i++ ) {
            comb[k] = i;
            bkt( k + 1, s2 );
        }
    }
}

std::vector<int> solve(std::vector<int> A) {
    n = A.size();
    v = A;
    int s, s2;

    s = 0;
    for( int i = 0; i < n; i++ ) {
        s += v[i];
    }

    s2 = ceil( float( s / 2 ) );
    mini = INT_MAX;
    bkt( 1, s2 );
    return rez;
}
