Submission

Score: 0

User: mik

Problemset: ประลอง

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-11 17:01:52

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>

using namespace std;

int n;
vector<int> arr;
int total_sum = 0;
int best_diff = INT_MAX;
vector<int> best_comb;
set<tuple<int, int, int>> memo;

void backtrack(int idx, int count, int current_sum, int target_k, vector<int>& current_comb) {
    if (count == target_k) {
        int diff = abs(total_sum - 2 * current_sum);
        if (diff < best_diff) {
            best_diff = diff;
            best_comb = current_comb;
        }
        return;
    }
    if (idx == n) return;
    if (count + (n - idx) < target_k) return;

    tuple<int, int, int> state = {idx, count, current_sum};
    if (memo.count(state)) return;

    current_comb.push_back(arr[idx]);
    backtrack(idx + 1, count + 1, current_sum + arr[idx], target_k, current_comb);
    current_comb.pop_back();

    backtrack(idx + 1, count, current_sum, target_k, current_comb);

    memo.insert(state);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n)) return 0;

    arr.resize(n);
    total_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        total_sum += arr[i];
    }

    vector<int> targets;
    if (n % 2 == 0) {
        targets = {n / 2};
    } else {
        targets = {n / 2, n / 2 + 1};
    }

    for (int target_k : targets) {
        memo.clear();
        vector<int> current_comb;
        backtrack(0, 0, 0, target_k, current_comb);
    }

    for (int i = 0; i < (int)best_comb.size(); ++i) {
        cout << best_comb[i] << (i == (int)best_comb.size() - 1 ? "" : " ");
    }
    cout << "\n";

    return 0;
}