第 255 场周赛 5853. 从子集的和还原数组

Rank 205，手速慢了。最后一题不会做。。。

Desciption

存在一个未知数组需要你进行还原，给你一个整数 n 表示该数组的长度。另给你一个数组 sums ，由未知数组中全部 2n 个 子集的和组成（子集中的元素没有特定的顺序）。

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

如果可以由数组 arr 删除部分元素（也可能不删除或全删除）得到数组 sub ，那么数组 sub 就是数组 arr 的一个 子集。sub 的元素之和就是 arr 的一个 子集的和。一个空数组的元素之和为 0 。

注意： 生成的测试用例将保证至少存在一个正确答案

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

示例：

输入：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] 能够满足给出的子集的和。

Solution

这个题在比赛的时候没有想出来，记录一下当时的思路

  1. 观察一下样例，比较容易看出来的是，sums里面的最大值肯定是所有正整数的和（如果没有正整数，最大值为空集的和 0），最小值是所有负整数的和（如果没有负整数，最小值为空集的和 0）
  2. 题目里给的 n 比较小，2^n 也才 3w+，考虑暴力的做法
  3. 怎么样求出数组里的数呢，有一个比较简单的想法：对 sums 数组进行排序，如果最小值 sums[0] 为 0，则其中有一个数肯定是 sums[1]；如果最大值 sum[len-1] 为 0，则其中有一个数肯定是 sums[len-2]；如果最小值 < 0，最大值 > 0，则有一个数为 sum[0] - sum[1], 另外一个数为 sum[len-1] - sum[len-2] （这个结论是错误的）
  4. 知道其中一些数后，则把这些数组成的集合的和，从 sums 数组中进行删除，进行下一轮迭代。 这样做的代码复杂度有点高，考虑到 n 不是很大，还是尝试这样写了一下，结果样例都没过就比赛结束了

看了一下题解，我的分析方法应该是对的，但是有两个地方我想错

  1. 我们已经知道：sums里面的最大值肯定是所有正整数的和（如果没有正整数，最大值为空集的和 0）。那思考一下，次大值是怎么来的？次大值可能是（最大值 - 原数组里最小的非负整数）or （最大值 + 原数组里最大的负整数），也就是说，我们用 最大值 - 次大值 得到的结果是原数组里某一个数的绝对值
  2. 假设这个数是一个 非负整数 x，我们该怎么过滤掉所有包含这个 x 的集合呢？首先最小值肯定是不会包含这个 x 的，因此我们就可以知道 最小值+x 可以被过滤掉。进而思考到如果把 最小值+x 放到队列里，再从小到大遍历 sums 数组，如果 sums[i] 出现在队列里，说明 sums[i] 包含了 x，否则就把 sums[i]+x 放到队列里。这样就过滤掉所有包含 x 的集合。如果 x 是负数，则从大到小遍历一遍
  3. 这样我们就可以得到不包含 x 的所有的集合的和，假设为 sub_sums，就又可以从第一步开始处理。由于我们只知道某一个数 x 的绝对值，因此我们需要把非负整数 和 负整数的场景都试一下，然后递归处理。复杂度（n * 2^n)
  4. 递归的停止条件是，sub_sums 的大小为2，即集合内只有一个数的场景，这时 sub_sums[0] 和 sum_sums[1] 肯定有一个为0，另外一个数则是数组里的数

Code

class Solution {
    public int[] recoverArray(int n, int[] sums) {
        Arrays.sort(sums);
        int len = sums.length;
        int[] ans = new int[n];
        if (n == 1) {
            ans[0] = sums[0] == 0 ? sums[1] : sums[0];
            return ans;
        }
        dfs(sums, ans, len, 0);
        return ans;
    }

    public boolean dfs(int[] sums, int[] ans, int len, int dep) {
        if (len == 2) {
            if (sums[1] != 0 && sums[0] != 0) {
                return false;
            }
            int x = sums[1] - sums[0];
            if (sums[1] == 0) {
                ans[dep] = -x;
            } else {
                ans[dep] = x;
            }
            return true;
        }
        int sub_len = len / 2;
        int[] new_sums = new int[sub_len];

        int x = sums[len - 1] - sums[len - 2];
        // x is abs(ans[dep]), if ans[dep] > 0
        Queue<Integer> q = new LinkedList<>();
        int cnt = 0;
        for (int i = 0; i < len; ++i) {
            if (q.isEmpty() || q.peek() != sums[i]) {
                q.add(sums[i] + x);
                if (cnt < sub_len) {
                    new_sums[cnt++] = sums[i];
                } else {
                    cnt++;
                }
            } else {
                q.poll();
            }
        }
        if (cnt == sub_len) {
            ans[dep] = x;
            if (dfs(new_sums, ans, sub_len, dep + 1)) {
                return true;
            }
        }

        // x is abs(ans[dep]), if ans[dep] < 0
        q.clear();
        cnt = sub_len - 1;
        for (int i = len - 1; i >= 0; --i) {
            if (q.isEmpty() || q.peek() != sums[i]) {
                q.add(sums[i] - x);
                if (cnt >= 0) {
                    new_sums[cnt--] = sums[i];
                } else {
                    cnt--;
                }
            } else {
                q.poll();
            }
        }
        if (cnt == -1) {
            ans[dep] = -x;
            if (dfs(new_sums, ans, sub_len, dep + 1)) {
                return true;
            }
        }

        return false;
    }
}