2016 年 408 真题
2016 年 408 数据结构 · 第 43 题
选中文字高亮 · 下划线
已知由 n(n≥2) 个正整数构成的集合 A=ak∣0≤k<n ，将其划分为两个不相交的子集 A1 和 A2 ，元素个数分别是 n1 和 n2 ， A1 和 A2 中元素之和分别为 S1 和 S2 。设计一个尽可能高效的划分算法，满足 ∣n1−n2∣ 最小且 ∣S1−S2∣ 最大。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。