\(3N\) 人を \(N\) 個の \(3\) 人組に分ける方法を全探索します。 まだどの組に入るか決めていない人のうち、最も番号の小さい人と組にする残りの \(2\) 人を決める、という操作を \(N\) 回行うことで組分けを全列挙することができます。

このとき探索する組み合わせの個数は、まだ組にしていない人のうち最も小さい番号の人は必ず組に入れることを考えると、残った人から \(2\) 人を選ぶ方法の数の総積となり、\(N=5\) の最大ケースで

\[ {}_{14} \mathrm{C}_2 \times {}_{11} \mathrm{C}_2 \times {}_{8} \mathrm{C}_2 \times {}_{5} \mathrm{C}_2 \times {}_{2} \mathrm{C}_2 \simeq 1.4 \times 10^6 \]

程度です。毎回 \(O(N^2)\) かけて組にする人を選んでも、計算回数は \(10^8\) 未満程度で実行時間に間に合わせることができます。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(3*n);
    for (int i=0; i<3*n; i++) cin >> a[i];
    auto f = [&] (auto self, int seen, int mx, int mn) -> int {
        if (seen == (1 << (3*n)) - 1) return mx - mn;
        int result = 1 << 30;
        int i = 0;
        for (int j=0; j<3*n; j++) if (!((seen >> j) & 1)) {i = j; break;}
        for (int j=i+1; j<3*n; j++) {
            if ((seen >> j) & 1) continue;
            for (int k=j+1; k<3*n; k++) {
                if ((seen >> k) & 1) continue;
                int total = a[i] + a[j] + a[k];
                int rn = self(self, seen | (1 << i) | (1 << j) | (1 << k), max(mx, total), min(mn, total));
                if (rn < result) result = rn;
            }
        }
        return result;
    };
    int ans = f(f, 0, 0, 1 << 30);
    cout << ans << '\n';
}