这道题是 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 属于 groupWithoutgroupWithout.add(s);countMap.put(s, countMap.get(s) - 1);// s diff 必须属于 groupWithcountMap.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。 总结这种分治 差值的方法是该题最主流的“最优解”写法。它避免了复杂的位运算枚举和最后的回溯修正直接通过数学性质“一刀切”地解决问题。