把一个数组分成两部分，求这两部分的差的最小值，怎么做？？（C++编程）

Question

Given you a list of numbers:
a[1], a[2], a[3],…,a[n].
You can divide them into two groups, A and B.
We define the sum of numbers in group A as sumA,
define the sum of numbers in group B as sumB.
Now you should let |sumA-sumB| as least as possible and output it.

Answer 1

迭代吧 

#include <stdio.h>
#include <math.h>
#define MAX 1000
int a[MAX],suma,sumb;
int sum(int xx,int len)
{
int i;
suma=0;sumb=0;
for(i=0;i<xx;i++)
{
suma+=a[i];
}
for(i=len-1;i>=xx;i--)
{
sumb+=a[i];
}
return abs(suma-sumb);
}
int main()
{
int n,min=999999,temp,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<n;i++)
{
temp=sum(i,n);
if(min==99999999)
{
min=temp;
}
else if(min>temp)
{
min=temp;
}
}
printf("%d\n", min);
}

追问

不对喔,输入4 1 2 3 4，输出2.答案是 0

追答

好吧 我弄错了 是分成 俩部分 不是分段
我想到暴力破解的方法 不知道 这题有没有 时间限制 还是 仅仅是作业 如果 算法速度 为 O（2^n）可以接受我写一遍

追问

可以的。n最大为20，数组的数最大为10^5，
但是我想不到怎么暴力。

追答//这道题是最基本的组合问题 
//zuhe[i]数值的0值代表 a[i] 左部分 1值代表 右部分 每次计算完毕 对组合更新
#include <stdio.h>
#include <string.h>
#include <math.h>
int main()
{
int zuhe[21],a[21],suma,sumb,min,n,i;
//接收
while(scanf("%d",&n),n>0)
{
min=20*500000;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}

//重置组合值为0
memset(zuhe,0,sizeof(zuhe));
//当组合未全部迭代过
while(zuhe[0]==0)
{
//根据组合值计算俩部分的 差值
suma=0;
sumb=0;
for(i=1;i<=n;i++)
{
if(zuhe[i]==0)
{
suma+=a[i];
}
else
{
sumb+=a[i];
}
if(min>abs(sumb-suma))
{
min=abs(sumb-suma);
}
}
//计算完毕后更新zuhe值
zuhe[n]++;
i=n;
while(zuhe[i]==2)
{
zuhe[i]=0;
zuhe[i-1]++;
i--;
}
}
//输出min
printf("%d\n", min);
}
return 0;
}

我测试了下  应该没问题了 输入小于0 结束 

关于这类 类型 可以去看看排列组合的