Subtask ~1~ ~(n \le 10)~

• Với mỗi ~a_i~, ta cho lần lượt vào từng tập và xóa khỏi từng tập (quay lui toàn bộ trường hợp).
• Đpt: ~(4^n)~.

Code tham khảo

#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
const int N = 20;

int n, a[N];
long long Min = 1e18, sum[3];
vector <int> chose[3], res[3];

void process() {
    long long Diff = max({sum[0], sum[1], sum[2]}) - min({sum[0], sum[1], sum[2]});
    if (Diff < Min) {
        Min = Diff;
        for (int i = 0; i < 3; i++) {
            res[i].clear();
            for (int val : chose[i]) res[i].push_back(val);
        }
    }
}

void back_track(int i) {
    if (i > n) return process();
    sum[0] += a[i];
    chose[0].push_back(a[i]);
    back_track(i + 1);
    sum[0] -= a[i];
    chose[0].pop_back();

    sum[1] += a[i];
    chose[1].push_back(a[i]);
    back_track(i + 1);
    sum[1] -= a[i];
    chose[1].pop_back();

    sum[2] += a[i];
    chose[2].push_back(a[i]);
    back_track(i + 1);
    sum[2] -= a[i];
    chose[2].pop_back();
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    back_track(1);
    if (Min == 0) cout << "Yes\n";
    else cout << Min << '\n';
    for (int i = 0; i < 3; i++) {
        for (int val : res[i]) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Subtask ~2~ ~(n \le 18)~.

• Nhận xét: Khi quay lui toàn bộ trường hợp sẽ xuất hiện các tập trùng (VD: ~[1, 2, 3], [1, 3, 2], [2, 1, 3], ...~).
• Để tránh lặp lại những trường hợp đã xét, ta đặt thêm cận như sau: chỉ thêm vị trí thứ ~i~ vào tập thứ ~k + 1~ khi tập ~k~ đã có phần tử và tập ~k + 1~ chưa có phần tử hoặc phần tử cuối cùng của tập ~k~ bé hơn ~i~.
• Đpt : ~4^n \div C^{n}_3~.

Code tham khảo của kieuphat159

#include <bits/stdc++.h>

using namespace std;
typedef int64_t ll;
const ll maxn = 20;

ll n, a[maxn];
ll Min = 1e18, sum[4];
vector <ll> res[4], pos[4];

void process()
{
    ll Diff = max({sum[1], sum[2], sum[3]}) - min({sum[1], sum[2], sum[3]});
    if (Diff == 0) {
        cout << "Yes\n";
        for (ll val : pos[1]) cout << a[val] << ' '; cout << '\n';
        for (ll val : pos[2]) cout << a[val] << ' '; cout << '\n';
        for (ll val : pos[3]) cout << a[val] << ' '; exit(0);
    }
    if (Diff < Min) {
        Min = Diff;
        res[1].clear(); for (ll val : pos[1]) res[1].push_back(val);
        res[2].clear(); for (ll val : pos[2]) res[2].push_back(val);
        res[3].clear(); for (ll val : pos[3]) res[3].push_back(val);
    }
}

void back_track(ll i)
{
    if (i > n) return process();

    sum[1] += a[i];
    pos[1].push_back(i);
    back_track(i + 1);
    sum[1] -= a[i];
    pos[1].pop_back();

    if ((pos[1].size() && !pos[2].size()) || (pos[1].back() < i)) {
        sum[2] += a[i];
        pos[2].push_back(i);
        back_track(i + 1);
        sum[2] -= a[i];
        pos[2].pop_back();
    }

    if ((pos[2].size() && !pos[3].size()) || (pos[2].back() < i)) {
        sum[3] += a[i];
        pos[3].push_back(i);
        back_track(i + 1);
        sum[3] -= a[i];
        pos[3].pop_back();
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    back_track(1);
    cout << Min << '\n';
    for (ll val : res[1]) cout << a[val] << ' '; cout << '\n';
    for (ll val : res[2]) cout << a[val] << ' '; cout << '\n';
    for (ll val : res[3]) cout << a[val] << ' ';
    return 0;
}