与2016年408数据结构考研的第43题很像，但做法完全不同，都是等分成两个数组，但是这道题要求最小化数组和的差。

方法一：DFS

DFS是暴力做法，递归枚举了所有的划分可能。时间复杂度：每层递归时间复杂度$O(1)$，取决于递归次数，总递归调用次数为组合数的累加：$$\sum_{i=0}^nC_{2n}^{i}$$，时间复杂度为$O(2^{2n})$。空间复杂度取决于递归层数，为$O(n)$。

int abs(int a){return a > 0 ? a : -a;}
int min(int a, int b){return a < b ? a : b;}
void dfs(const int* nums,int now,const int tot, int sum, int cnt,const int target, int *ans){
    if(cnt == target){
        *ans = min(*ans, abs(tot - sum - sum));
        return;
    }
    for(int i = now; i < target * 2; i++){
        dfs(nums, i + 1, tot, sum + nu ms[i], cnt + 1, target, ans);
    }
};
int minimumDifference(int* nums, int numsSize) {
    int sum = 0;
    for(int i = 0; i < numsSize; i++)sum += nums[i];
    int ans = 1e8;
    dfs(nums, 0, sum, 0, 0, numsSize / 2, &ans);
    return ans;
}

方法二：折半枚举+排序+二分

两个数组和之差可以视作从 nums 中选 n 个数取正号，其余 n 个数取负号，然后求元素和。

我们可以使用折半枚举的方法，枚举 nums 的前 n 个元素取正或取负的所有情况，按取正的个数分组，并在组中按照元素和排序。然后枚举 nums 的后 n 个元素取正或取负的所有情况，然后去对应的组里二分找元素和最近的数，答案即为所有情况中最小的差值。