#include <bits/stdc++.h>
#include "partition.h"
#define int long long 
#define endl '\n'

using namespace std;

const int MAXN = 20;

int n, ans;
bool used[MAXN + 5];
vector<int>otg, v;
double a[MAXN + 5], s;

void check()
{
    double sum = 0;
    bool f = true;
    for(int i = 0; i < v.size(); i++)
    {
        sum += a[v[i]];
        if(sum >= s / 2.0)
        {
            if(i != v.size() - 1)
            {
                f = false;
            }

            break;
        }
    }
    if(!(sum >= s / 2.0))
    {
        f = false;
    }

    if(f)
    {
        int curr = abs((n - (int)v.size()) - (int)v.size());
        if(ans > curr)
        {
            ans = curr;
            otg = v;
        }
    }
}

void rec(int pos)
{
    if(pos == n)
    {
        check();
        return;
    }

    v.push_back(pos);
    rec(pos + 1);
    v.pop_back();
    rec(pos + 1);
}

std::vector<int> solve(std::vector<int> A)
{
    n = A.size();
    s = 0;
    otg.clear();

    for(int i = 0; i < A.size(); i++)
    {
        a[i] = A[i];
        s += A[i];
    }

    ans = 1e9;
    rec(0);

    memset(used, false, sizeof(used));
    for(auto i: otg)
    {
        used[i] = true;
    }

    for(int i = 0; i < n; i++)
    {
        if(!used[i])otg.push_back(i);
    }

    return otg;
}
