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

using namespace std;

std::vector<int> solve(std::vector<int> A) {
    vector <int> bestAns;
    int bestBagsDelta = 1e9;
    int S, n = A.size();
    for(int i = 0; i < n; i++)
        S += A[i];

    for(int i = 1; i <= 5100; i++)
    {
        //for(int j : A)
        //    cout << j << ' ';
        //cout << endl;

        int s = 0;
        int bags = 0;
        while(s < S / 2)
        {
            s += A[bags];
            bags++;
        }
        bags = abs(n - (2 * bags));

        if(bags < bestBagsDelta)
        {
            bestBagsDelta = bags;
            bestAns = A;
        }

        next_permutation(A.begin(), A.end());
    }

    return bestAns;
}
