#include "partition.h"
#include <bits/stdc++.h>
#define MAXVAL 30000000
#define MAXN 2000
#define INF 1000000000

using namespace std;

int per[MAXN + 1], mini, ind, per_min[MAXN + 1], frecv[MAXN + 1];

void bkt(int pos, int cur, int sum, vector <int> A){
    int i;
    if(cur >= sum / 2){
        if(cur < mini){
            mini = cur;
            ind = pos;
            for(i = 1; i < pos; i++){
                per_min[i] = per[i];
            }
        }
    }else{
        for(i = 0; i < A.size(); i++){
            if(frecv[i] == 0){
                frecv[i] = 1;
                per[pos] = i;
                bkt(pos + 1, cur + A[i], sum, A);
                frecv[i] = 0;
            }
        }
    }
}

vector<int> solve(vector<int> A){
    int N, i, sum;
    vector <int> rez;

    N = A.size();
    sum = 0;
    for(i = 0; i < N; i++){
        sum += A[i];
    }

    mini = INF;
    bkt(1, 0, sum, A);
    for(i = 1; i < ind; i++){}
    return rez;
}
//5
//4
//1 2 4 8
//5
//1 2 4 8 16
