题目分析

已知 $n$ 个不同正整数的所有两两和（共 $\frac{n(n-1)}{2}$ 个），要求还原出所有可能的原数集合。

---

核心思路

1. 数学推导

设原数为 $a_1 < a_2 < \dots < a_n$，则有：

• $a_1 + a_2 = s_{\min}$（最小的和）
• $a_1 + a_3 = s_{\text{第二小}}$（第二小的和）
• $a_2 + a_3 = s_k$（某个未知的和）

由这三个方程可以解出：

$$a_1 = \frac{(a_1+a_2) + (a_1+a_3) - (a_2+a_3)}{2} = \frac{s_1 + s_2 - s_k}{2} $$$$a_2 = s_1 - a_1,\quad a_3 = s_2 - a_1$$

2. 算法流程

1. 排序：将所有两两和排序
2. 枚举候选：枚举 $s_k$ 作为 $a_2 + a_3$ 的可能值
3. 计算前三个数：用上述公式计算 $a_1, a_2, a_3$
4. 验证并构造：用 multiset 逐步构造剩余的数并验证

---

代码解析

for (ll i = 3; i <= n; ++i) {
    // 跳过重复值
    if (i != 3 && s[i] == s[i - 1]) continue;
    
    // 检查奇偶性和正数条件
    if (((s[1] + s[2] - s[i]) & 1) || s[1] + s[2] - s[i] <= 0)
        continue;
    
    // 计算前三个数
    a[1] = (s[1] + s[2] - s[i]) / 2;
    val.clear();
    for (ll i = 1; i <= n * (n - 1) / 2; ++i)
        val.insert(s[i]);
    
    bool ok = 1;
    // 构造剩余的数
    for (ll j = 2; j <= n; ++j) {
        a[j] = *val.begin() - a[1];
        
        // 检查递增性
        if (a[j] < a[j - 1]) {
            ok = 0;
            break;
        }
        
        // 验证所有两两和
        for (ll k = 1; k < j; ++k)
            if (val.find(a[j] + a[k]) != val.end())
                val.erase(val.find(a[j] + a[k]));
            else {
                ok = 0;
                break;
            }
        
        if (!ok) break;
    }
    
    if (ok) {
        ++cnt;
        for (ll i = 1; i <= n; ++i)
            ans[cnt][i] = a[i];
    }
}

---

关键优化

1. 跳过重复值：相同的 $s_k$ 会产生相同解
2. 奇偶性检查：确保 $a_1$ 是整数
3. 递增性检查：确保序列严格递增
4. 及时终止：发现不合法立即跳出循环

---

复杂度分析

• 时间复杂度：$O(n^4 \log n)$
  • 外层循环：$O(n)$
  • 内层构造：$O(n^2)$
  • multiset 操作：$O(\log n)$
• 空间复杂度：$O(n^2)$

---

样例验证

样例1：

输入：n=4, 和=[3,5,4,7,6,5]
排序后：[3,4,5,5,6,7]

枚举 s[3]=5：
a1 = (3+4-5)/2 = 1
a2 = 3-1 = 2  
a3 = 4-1 = 3
构造 a4 = 5-1 = 4
验证通过 → 输出 [1,2,3,4]

样例2：

输入：n=4, 和=[11,17,12,20,21,15]
排序后：[11,12,15,17,20,21]

找到两个解：
[3,8,9,12] 和 [4,7,8,13]

---

总结

该解法通过：

1. 数学推导确定前三个数的关系
2. 枚举验证所有可能的 $a_2+a_3$ 候选值
3. 贪心构造剩余数字并验证两两和

虽然理论复杂度较高，但由于 $n \leq 300$ 且很多候选会被快速排除，实际运行效果良好。