#include "partition.h"
#include<algorithm>
#include<set>
using namespace std;

vector<int> a;


int S2 = 0;
int target;
bool check_perm(vector<int> &p) {
    int cnt = 0;
    int sum = 0;
    for(int i = 0; i < p.size() && sum < S2; i++) {
        cnt++;
        sum += a[p[i]];
    }

    return cnt == target;
}

std::vector<int> solve(std::vector<int> A) {
    vector<int> perm;
    a.clear();
    S2 = 0
    target = A.size() / 2 + A.size() % 2;

    for(int i = 0; i < A.size(); i++) {
        perm.push_back(i);
        S2 += A[i];
        a.push_back(A[i]);
    }
    S2 += S2 % 2;
    S2 /= 2;

    while(!check_perm(perm)) {
        next_permutation(perm.begin(), perm.end());
    }
    return perm;
}

