Hard

题目描述

给你一个整数 n，表示一个你正试图恢复的未知数组的长度。同时给你一个数组 sums，其中包含未知数组所有 2^n 个子集和的值（顺序任意）。

返回长度为 n 的数组 ans，表示未知数组。如果存在多个答案，返回其中任意一个。

如果数组 sub 可以通过删除数组 arr 的某些（可能是零个或全部）元素得到，那么数组 sub 就是数组 arr 的一个子集。sub 中元素的和是 arr 的一个可能的子集和。空数组的和被认为是 0。

注意：测试用例保证至少存在一个正确答案。

示例 1：

输入：n = 3, sums = [-3,-2,-1,0,0,1,2,3]
输出：[1,2,-3]
解释：[1,2,-3] 能够生成给定的子集和：
- []：和为 0
- [1]：和为 1
- [2]：和为 2
- [1,2]：和为 3
- [-3]：和为 -3
- [1,-3]：和为 -2
- [2,-3]：和为 -1
- [1,2,-3]：和为 0

示例 2：

输入：n = 2, sums = [0,0,0,0]
输出：[0,0]
解释：唯一正确答案是 [0,0]。

示例 3：

输入：n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]
输出：[0,-1,4,5]
解释：[0,-1,4,5] 能够生成给定的子集和。

约束条件：

  • 1 <= n <= 15
  • sums.length == 2^n
  • -10^4 <= sums[i] <= 10^4

解题思路

这道题的核心思想是递归分治。通过观察可以发现，如果我们知道原数组的一个元素 x，那么所有子集和可以分为两组：包含 x 的子集和与不包含 x 的子集和。

解题思路：

  1. 排序处理：首先对 sums 排序，最小值一定是所有负数的和（如果有的话），最大值一定是所有正数的和。

  2. 确定差值：第二小的值与最小值的差，就是原数组中绝对值最小的非零元素（如果存在）。

  3. 分组递归：假设当前要确定的元素是 diff，我们将当前的子集和分为两组：

    • 一组包含这个元素 diff
    • 一组不包含这个元素

    包含 diff 的子集和减去 diff 后，应该与不包含 diff 的子集和形成相同的多重集合。

  4. 验证选择：通过贪心匹配验证我们的选择是否正确。如果能完美匹配，说明我们找到了正确的元素。

  5. 递归求解：移除确定的元素后，对剩余的子集和递归求解。

这个算法的时间复杂度主要取决于每层递归中的匹配过程，空间复杂度为递归深度。由于 n ≤ 15，这个方法是可行的。

代码实现

class Solution {
public:
    vector<int> recoverArray(int n, vector<int>& sums) {
        if (n == 1) return {sums[1] - sums[0]};
        
        sort(sums.begin(), sums.end());
        int diff = sums[1] - sums[0];
        
        multiset<int> with, without;
        for (int sum : sums) {
            with.insert(sum);
        }
        
        for (int sum : sums) {
            if (with.count(sum) && with.count(sum + diff)) {
                without.insert(sum);
                with.erase(with.find(sum));
                with.erase(with.find(sum + diff));
            }
        }
        
        vector<int> withoutVec(without.begin(), without.end());
        vector<int> result = recoverArray(n - 1, withoutVec);
        
        // 验证选择正确性
        multiset<int> expected;
        for (int sum : without) {
            expected.insert(sum);
            expected.insert(sum + diff);
        }
        
        multiset<int> actual(sums.begin(), sums.end());
        if (expected == actual) {
            result.push_back(diff);
        } else {
            result.push_back(-diff);
        }
        
        return result;
    }
};

class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        if n == 1:
            return [sums[1] - sums[0]]
        
        sums.sort()
        diff = sums[1] - sums[0]
        
        with_count = Counter(sums)
        without = []
        
        for sum_val in sums:
            if with_count[sum_val] > 0 and with_count[sum_val + diff] > 0:
                without.append(sum_val)
                with_count[sum_val] -= 1
                with_count[sum_val + diff] -= 1
        
        result = self.recoverArray(n - 1, without)
        
        # 验证选择正确性
        expected = Counter()
        for sum_val in without:
            expected[sum_val] += 1
            expected[sum_val + diff] += 1
        
        actual = Counter(sums)
        if expected == actual:
            result.append(diff)
        else:
            result.append(-diff)
        
        return result

public class Solution {
    public int[] RecoverArray(int n, int[] sums) {
        if (n == 1) return new int[] { sums[1] - sums[0] };
        
        Array.Sort(sums);
        int diff = sums[1] - sums[0];
        
        var withCount = new Dictionary<int, int>();
        foreach (int sum in sums) {
            withCount[sum] = withCount.GetValueOrDefault(sum, 0) + 1;
        }
        
        var without = new List<int>();
        
        foreach (int sum in sums) {
            if (withCount.GetValueOrDefault(sum, 0) > 0 && 
                withCount.GetValueOrDefault(sum + diff, 0) > 0) {
                without.Add(sum);
                withCount[sum]--;
                withCount[sum + diff]--;
            }
        }
        
        var result = new List<int>(RecoverArray(n - 1, without.ToArray()));
        
        // 验证选择正确性
        var expected = new Dictionary<int, int>();
        foreach (int sum in without) {
            expected[sum] = expected.GetValueOrDefault(sum, 0) + 1;
            expected[sum + diff] = expected.GetValueOrDefault(sum + diff, 0) + 1;
        }
        
        var actual = new Dictionary<int, int>();
        foreach (int sum in sums) {
            actual[sum] = actual.GetValueOrDefault(sum, 0) + 1;
        }
        
        bool isValid = expected.Count == actual.Count && 
                       expected.All(kv => actual.GetValueOrDefault(kv.Key, 0) == kv.Value);
        
        if (isValid) {
            result.Add(diff);
        } else {
            result.Add(-diff);
        }
        
        return result.ToArray();
    }
}

var recoverArray = function(n, sums) {
    sums.sort((a, b) => a - b);
    
    function solve(arr) {
        if (arr.length === 1) return [];
        
        const diff = arr[1] - arr[0];
        const with0 = [];
        const with1 = [];
        const count = new Map();
        
        for (const num of arr) {
            count.set(num, (count.get(num) || 0) + 1);
        }
        
        for (const num of arr) {
            if (count.get(num) > 0) {
                with0.push(num);
                count.set(num, count.get(num) - 1);
                
                const target = num + diff;
                if (count.get(target) > 0) {
                    with1.push(target);
                    count.set(target, count.get(target) - 1);
                }
            }
        }
        
        if (with0.includes(0)) {
            return [diff].concat(solve(with0));
        } else {
            return [-diff].concat(solve(with1));
        }
    }
    
    return solve(sums);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × 2^n)每层递归需要处理 2^(n-i) 个元素，共 n 层
空间复杂度O(2^n)递归栈深度为 n，每层存储子集和数组

相关题目