给定n个整数，请将这n个整数分为两部分（个数不一定要等），使得第一部分的和大于且尽量接近第二部分的和的两倍。

Question

D98jc. 集合划分
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：3分钟(现在可以提交)
输入文件名：sets.in 输出文件名：sets.out
问题描述
　　给定n个整数，请将这n个整数分为两部分（个数不一定要等），使得第一部分的和大于且尽量接近第二部分的和的两倍。
输入格式
　　从文件sets.in中读入数据。
　　输入的第一行包含一个整数n。
　　第二行包含n个整数，表示给定的数。
输出格式
　　输出到文件sets.out中。
　　你不需要输出具体的划分方案，只要输出第一部分的和减去第二部分的和的两倍的值。
样例输入
4
3 8 7 4
样例输出
1
样例说明
　　3, 8, 4为一部分，7为另一部分，(3+8+4)–2×7=1。
数据规模和约定
　　对于40%的数据，1 ≤ n ≤ 20，给定的每个数为不超过100的正整数。
　　对于100%的数据，1 ≤ n ≤ 100，给定的每个数为不超过1000的正整数。

Answer 1

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

const int MAXN = 20;
int n;
int a[MAXN];

int solve(int k, int sum1, int sum2) {
    if (k == n) return abs(sum1 - 2 * sum2);
    int ans1 = solve(k + 1, sum1 + a[k], sum2); // 将a[k]分到第一部分
    int ans2 = solve(k + 1, sum1, sum2 + a[k]); // 将a[k]分到第二部分
    return min(ans1, ans2);
}

int main() {
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    cout << solve(0, 0, 0) << endl;
    return 0;
}