cses 16：数组拆分问题

描述

将一个数组分成两部分，使这两部分的和之差最小，求这个最小差值

分析

这题是一道非常经典的选数问题，思路是在一个数组中选一些数，使这些数的和在不大于数组元素总和一半 的前提下尽可能大。
首先这一题我优先想到的解法是 背包，开一个长度为 的数组滚动求解，时间复杂度 ，空间复杂度 ，但是在这一题中， 的值可以达到非常大，我们开不了那么大的空间，所以并不合适。
注意到 的范围很小，所以可以采取暴力搜索的办法，可以根据 的值进行剪枝优化，时间复杂度 ，空间复杂度

代码

// 分苹果问题
#include <cstdio>

typedef long long ll;
int a[25], n;
ll sm, ans;

void dfs(int cur, ll val) { // 第二个参数类型必须设为长整型，否则容易出错
    if (val * 2 > sm) return;
    if (cur == n) {
        if (val > ans) ans = val; // 剪枝优化
        return;
    }
    
    dfs(cur + 1, val + a[cur]);
    dfs(cur + 1, val);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        sm += a[i];
    }
    
    dfs(0, 0);
    printf("%lld\n", sm - ans - ans);
    return 0;
}