给定所有子集和，含负数的集合还原算法求解

前提条件 #

输入的子集和集合包含空集的和（0），且所有子集和无重复，长度为2^k（k是原集合A的元素个数）。

算法步骤 #

1. 排序去重
   将输入的子集和数组排序并去除重复元素，得到有序数组S。先检查S的长度是否为2的幂，若不是则输入无效。

2. 递归构建原集合
   定义递归逻辑处理当前子集和集合：

   • 若集合长度为1（只剩0），返回空集合。
   • 取当前集合的最小非零元素min_val和最大非零元素max_val作为候选元素。
   • 验证候选元素是否属于原集合：
     对于候选元素x，利用有序数组的双指针法检查：是否能将S中的元素两两配对，每对满足a = b + x，且所有元素都被覆盖（共len(S)/2对）。若满足，则x是原集合元素。
   • 找到符合条件的x后，提取不包含x的子集和集合T（即配对中的b组成的集合），递归处理T，将递归结果与x合并。
   • 返回合并后的集合。

示例演示 #

以输入0 -2 4 5 2 3 9 7为例：

1. 排序后S = [-2, 0, 2, 3, 4, 5, 7, 9]，长度8=2^3，k=3。
2. 取候选元素min_val=-2，用双指针法验证：
   可配对为(-2,0)、(2,4)、(3,5)、(7,9)，共4对覆盖所有元素，说明-2是原集合元素。提取不包含-2的子集和集合T = [0,4,5,9]。
3. 递归处理T：
   取候选元素4，配对为(0,4)、(5,9)，覆盖所有元素，提取T' = [0,5]。
4. 递归处理T'：
   取候选元素5，配对为(0,5)，覆盖所有元素，提取[0]，递归返回空集。
5. 合并结果：5 → {4,5} → {-2,4,5}，得到正确原集合。

时间复杂度分析 #

每次递归处理的数组大小是前一次的一半，每次验证和提取子集的操作基于有序数组，时间为O(m)。总时间为：
O(n log n + n/2 log(n/2) + n/4 log(n/4) + ...) = O(n log n)
符合要求的时间复杂度。

内容的提问来源于stack exchange，提问作者fmatt