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

using namespace std;
const int MAXN = 20;

vector<int> rez;
vector<int> v;
int comb[MAXN + 1]; //submultimea indicilor din grupa A
bool f[MAXN + 1];
int mini, n;
long long s2;
int vf[MAXN + 1];

void bkt( int k ) {
    long long sumA;
    if( k <= n ) {
        int i, cntA, cntB, diff, flag;
        sumA = 0;
        cntA = cntB = diff = flag = 0;
        for( i = 0; i < k; i++ ) {
            cntA++;
            sumA += v[comb[i]];
            if( sumA >= s2 )
                flag++;
        }
        cntB = n - cntA;
        diff = abs( cntA - cntB );
        if( flag == 1 && diff < mini ) {
            mini = diff;
            memset( vf, 0, sizeof( vf ) );
            for( i = 0; i < k; i++ ) {
                rez[i] = comb[i];
                vf[comb[i]] = 1;
            }
            for( i = 0; i < n; i++ )
                if( vf[i] == 0 )
                    rez[i] = i;
            //for( i = 0; i < n; i++ )
            //    if( comb[i] == 0 )
            //        ind.push_back( i );
            //for( ; i < n; i++ )
            //    if( !f[i] )
            //        rez[i] = i;
            //rez = ind;
        }

        for( i = 0; i < n; i++ ) {
            if( f[i] == 0 ) {
                f[i] = 1;
                comb[k] = i;
                bkt( k + 1 );
                f[i] = 0;
            }
        }
    }
}

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

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

    s2 = s / 2 + s % 2;
    mini = INT_MAX;
    rez.resize( n );
    for( int i = 0; i < n; i++ )
        f[i] = comb[i] = rez[i] = 0;
    bkt( 0 );
    //cout << mini << '\n';
    return rez;
}
