#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'

vector<int> solve(vector<int> A)
{
    int n = A.size();
    int half_s = accumulate(A.begin(),A.end(),0) / 2, ans = 1e9;

    vector<int>optimal,curr(n);
    iota(curr.begin(),curr.end(), 0);

    do
    {
        int sum = 0,idx = 0;
        while(sum < half_s)
            sum += A[curr[idx++]];

        int curr_diff =abs(n-2*idx+1);
        if(curr_diff < ans){
            ans = curr_diff;
            optimal = curr;
        }
    }
    while(next_permutation(curr.begin(),curr.end()));

    return optimal;
}
