)
这道题是 LeetCode 1982 从子集的和还原数组，属于比较困难的构造/回溯类题目。
它的核心难点在于：给定的 sums 数组包含了原数组所有子集的和（共 2^n 个），且原数组中可能包含负数。如果全是正数，这道题会简单很多；一旦涉及负数，我们需要通过数学变换将其转化为非负数问题来处理。
以下是详细的解题思路和 Java 代码实现。
💡 核心思路
1. 处理负数（关键步骤）：
* 如果数组中包含负数，sums 中的最小值（记为 minSum）一定是原数组中所有负数之和。
* 为了简化问题，我们可以假设将所有负数取反，这样所有子集的和都会增加 abs(minSum)。
* 因此，我们先把 sums 中的每个数都加上 abs(minSum)，将其转化为一个全为非负数的问题来求解。
* 最后，在还原出的数组中，我们需要找到一个子集，其和等于 abs(minSum)，并将该子集中的元素全部取反，从而还原出真正的负数。
2. 构造非负数组：
* 对于非负数组，sums 排序后，除去 0（空集）以外的最小值，一定是原数组中的最小元素。
* 我们可以使用 HashMap 或 Multiset 来记录当前剩余可用的子集和。
* 每次取出最小的可用和作为原数组的一个元素，然后从集合中移除该元素能组成的所有新子集和。
3. 恢复符号：
* 得到非负数组后，利用回溯或状态压缩找到一个子集，使其和等于 abs(minSum)，将这些元素取反即可。
💻 Java 代码实现
import java.util.*;
class Solution {
public int[] recoverArray(int n, int[] sums) {
// 1. 找出 sums 中的最小值，用于处理负数情况
// 最小值一定是原数组中所有负数之和
int minSum = Integer.MAX_VALUE;
for (int sum : sums) {
minSum = Math.min(minSum, sum);
}
// 计算偏移量，将所有和变为非负数
int offset = -minSum;
// 2. 将 sums 中的所有值加上 offset，转化为非负数问题
// 同时使用 HashMap 统计每个和出现的次数
Map countMap = new HashMap();
for (int sum : sums) {
countMap.put(sum + offset, countMap.getOrDefault(sum + offset, 0) + 1);
}
// 移除一个 0 (空集的和)，因为我们要开始找非零元素了
// 注意：这里是在偏移后的空间里操作
countMap.put(0, countMap.get(0) - 1);
// 对 sums 进行排序，方便从小到大取最小值
// 注意：这里我们需要对原始 sums 排序后再加 offset，或者直接对变换后的值排序
// 为了逻辑清晰，我们重新构建一个排序后的列表用于遍历
List sortedSums = new ArrayList();
for (int sum : sums) {
sortedSums.add(sum + offset);
}
Collections.sort(sortedSums);
int[] ans = new int[n];
int idx = 0;
// 3. 贪心构造非负数组
for (int sum : sortedSums) {
// 如果当前和已经被移除完了，跳过
if (countMap.getOrDefault(sum, 0) == 0) {
continue;
}
// 当前最小的可用和就是原数组的一个元素
ans[idx] = sum;
idx++;
// 从 countMap 中移除由 ans[idx-1] 产生的所有子集和
// 这些新产生的和 = 旧子集和 + ans[idx-1]
// 我们只需要遍历当前已找到的 ans 元素的所有子集组合
removeSums(countMap, ans, idx);
}
// 4. 恢复负数
// 我们需要在 ans 中找到一个子集，其和等于 offset
// 将该子集中的所有元素取反
flipNegatives(ans, offset);
return ans;
}
// 移除由新加入元素 val (即 ans[size-1]) 产生的所有子集和
private void removeSums(Map map, int[] ans, int size) {
// 遍历所有包含 ans[size-1] 的子集
// 使用位运算枚举子集
int totalSubsets = 1 << size;
// 从 1 << (size - 1) 开始，确保每个子集都包含最后一个元素 ans[size-1]
for (int i = 1 << (size - 1); i < totalSubsets; i++) {
int sum = 0;
for (int j = 0; j < size; j++) {
if ((i & (1 << j)) != 0) {
sum += ans[j];
}
}
map.put(sum, map.get(sum) - 1);
}
}
// 找到和为 target 的子集，并将其元素取反
private void flipNegatives(int[] ans, int target) {
int n = ans.length;
int total = 1 << n;
for (int i = 0; i < total; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
sum += ans[j];
}
}
if (sum == target) {
// 找到了，取反
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
ans[j] = -ans[j];
}
}
return;
}
}
}
}
📝 代码详解
1. 偏移量处理 (offset)：
* 我们首先找到 sums 的最小值。假设原数组负数和为 -5，那么 sums 里最小就是 -5。
* 我们将所有 sums 加上 5，这样最小值变成了 0。此时问题等价于：原数组里的负数都变成了正数。
2. 贪心构造 (removeSums)：
* 在变换后的非负世界里，排序后的 sums 中第一个非 0 的数一定是原数组的最小值。
* 一旦确定了一个元素 x，所有包含 x 的子集和都可以表示为 old_sum + x。
* 我们需要从哈希表中减去这些组合的数量，剩下的最小数就是下一个元素。
3. 符号还原 (flipNegatives)：
* 我们构造出的 ans 数组全是正数（或0），它们的子集和对应的是 sums + offset。
* 为了让子集和变回原来的 sums，我们需要把某些正数变回负数。
* 变回负数会导致总和减少。我们需要减少的总量正好是 offset。
* 所以，只要在 ans 中找到和为 offset 的子集，把它们取反，就能完美还原。
⏱️ 复杂度分析
* 时间复杂度：O(N cdot 2^N)。
* 排序 sums 需要 O(2^N log 2^N) = O(N cdot 2^N)。
* 构造数组时，我们需要遍历 2^N 个和，每次移除子集和操作涉及位运算，最坏也是 O(N cdot 2^N) 级别。
* 最后寻找取反子集也是 O(N cdot 2^N)。
* 空间复杂度：O(2^N)，用于存储哈希表和排序数组。
针对 LeetCode 1982 从子集的和还原数组，其实是有更优、更简洁的解法的。
之前的解法虽然逻辑严密，但代码量较大，且需要显式地处理“偏移量”和最后的“符号还原”。
这里介绍一种基于分治（Divide and Conquer）的递归解法。这种方法代码更短，逻辑更直观，且不需要在最后单独进行符号翻转。
💡 核心思路：分治与差值法
这个解法的核心在于利用排序后数组的性质，通过差值来直接确定元素，并利用分组来递归求解。
1. 排序与差值：
将 sums 排序。对于任意一个原数组中的元素 x（假设 x ge 0），如果我们把所有子集分为“包含 x”和“不包含 x”两类，那么“包含 x”的子集和一定比对应的“不包含 x”的子集和大 x。
因此，排序后的 sums 中，第二小的数减去最小的数（即 sums[1] - sums[0]），其绝对值一定是原数组中某个元素的绝对值。
2. 分组策略：
我们假设这个差值 d = text{sums}[1] - text{sums}[0] 是原数组中的一个元素。
我们需要将 sums 数组切分成两个部分：
* 组 A：不包含元素 d 的子集和。
* 组 B：包含元素 d 的子集和。
显然，组 B 中的每个数减去 d 应该等于组 A 中的对应数。我们可以用双指针或哈希表来完成这个配对和拆分。
3. 判断正负（关键优化）：
拆分后，我们需要决定 d 是正数还是负数（即 d 还是 -d）。
* 判定依据：如果原数组包含负数，那么所有负数之和一定是 sums 中的最小值。
* 在递归过程中，如果某一组的最小值为 0，说明这一组对应的子问题中没有负数（或者说负数已经被处理完了/不存在）。
* 规则：
* 如果组 A 的最小值是 0，说明我们可以选 d 为正数，递归求解组 A。
* 否则，说明 d 必须是负数（即 -d），此时我们应该递归求解组 B（因为组 B 相当于把 -d 拿走后剩下的部分，或者说组 B 对应的是包含 d 的情况，我们需要调整逻辑）。
* 更简单的判断：只要看拆分出来的不包含当前差值的那一组（即较小的那一组），如果它的最小值是 0，那我们就选正的 d；否则选 -d。
💻 更优的 Java 代码实现
import java.util.*;
class Solution {
public int[] recoverArray(int n, int[] sums) {
Arrays.sort(sums);
List ans = new ArrayList();
solve(sums, ans);
return ans.stream().mapToInt(i -> i).toArray();
}
private void solve(int[] sums, List ans) {
int m = sums.length;
// 递归终止条件：只剩下一个元素（必然是0，空集的和）
if (m == 1) return;
// 1. 计算差值，这一定是某个元素的绝对值
int diff = sums[1] - sums[0];
// 2. 尝试将 sums 分为两组：
// groupWithout: 不包含 diff 的子集和
// groupWith: 包含 diff 的子集和
List groupWithout = new ArrayList();
List groupWith = new ArrayList();
// 使用 HashMap 记录每个数出现的次数，处理重复值
Map countMap = new HashMap();
for (int s : sums) {
countMap.put(s, countMap.getOrDefault(s, 0) + 1);
}
for (int s : sums) {
if (countMap.get(s) == 0) continue;
// s 属于 groupWithout
groupWithout.add(s);
countMap.put(s, countMap.get(s) - 1);
// s + diff 必须属于 groupWith
countMap.put(s + diff, countMap.get(s + diff) - 1);
groupWith.add(s + diff);
}
// 3. 判断 diff 是正还是负
// 如果 groupWithout 中包含 0，说明这组是“非负”的基础组，diff 取正值
// 否则 diff 取负值
boolean hasZero = groupWithout.contains(0);
if (hasZero) {
ans.add(diff); // 选正数
solve(groupWithout.stream().mapToInt(i->i).toArray(), ans);
} else {
ans.add(-diff); // 选负数
solve(groupWith.stream().mapToInt(i->i).toArray(), ans);
}
}
}
🚀 为什么这个解法更优？
1. 逻辑闭环：不需要像第一种解法那样先整体偏移、最后再找子集翻转。它在递归的过程中直接确定了每个数的正负。
2. 代码简洁：利用 HashMap 处理配对，逻辑非常清晰。
3. 数学性质利用：利用了“如果存在负数，最小和必为负数和”这一性质，通过检查 0 是否存在来动态决定符号。
📊 复杂度分析
* 时间复杂度：O(N cdot 2^N)。
* 每一层递归处理 2^k 个元素，共有 N 层。
* 虽然用了 HashMap，但整体操作次数依然与子集总数线性相关。
* 空间复杂度：O(2^N)，用于存储临时的分组列表和 HashMap。
📌 总结
这种分治 + 差值的方法是该题最主流的“最优解”写法。它避免了复杂的位运算枚举和最后的回溯修正，直接通过数学性质“一刀切”地解决问题。
