2016年408算法大题
已知由n（n>=2）个正整数构成的集合A ，将其划分成两个不相交的子集A1和A2，元素个数分别为n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：1）给出算法的基本设计思想。2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。3）说明你所设计算法的平均时间复杂度和空间复杂度。【解析】（1）根据快速排序的思想，把找到最佳的划分，把最小的[n/2]个数放到A1，其余的数放到A2。分组结果即为题意
