【正经题解】Gold King的财富

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

const int MAX_N = 25;
int n, assets[MAX_N], minDifference = INT_MAX;

// 递归计算资产分配的最小差值
void dfs(int index, int sumA, int sumB) {
    if (index == n + 1) {
        int difference = abs(sumA - sumB);
        minDifference = min(minDifference, difference);
        return;
    }

    // 尝试将资产分配给 A
    dfs(index + 1, sumA + assets[index], sumB);
    
    // 尝试将资产分配给 B
    dfs(index + 1, sumA, sumB + assets[index]);
}

int main() {
    cin >> n;

    // 输入资产价值
    for (int i = 1; i <= n; i++) {
        cin >> assets[i];
    }

    // 降序排列资产价值
    sort(assets + 1, assets + n + 1, greater<int>());

    // 递归计算最小差值
    dfs(1, 0, 0);

    // 输出结果
    cout << minDifference << endl;

    return 0;
}