1982. 从子集的和还原数组Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

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

如果可以由数组 arr 删除部分元素（也可能不删除或全删除）得到数组 sub ，那么数组 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
注意，[1,2,-3] 的任何排列和 [-1,-2,3] 的任何排列都会被视作正确答案。

示例 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ⁿ
-104 <= sums[i] <= 10⁴

# 思路

dfs

# 解法

class Solution {

    public int[] recoverArray(int n, int[] sums) {
        Arrays.sort(sums);
        List<Integer> list = dfs(n, sums);
        int[] ans = new int[n];
        int index = 0;
        for (Integer num : list) ans[index++] = num;
        return ans;
    }

    private List<Integer> dfs(int n, int[] sums) {
        if (n == 1) {
            List<Integer> ans = new ArrayList<>();
            if (sums[0] == 0) ans.add(sums[1]);
            else if (sums[1] == 0) ans.add(sums[0]);
            return ans;
        }

        int delta = sums[1] - sums[0];
        int[] s = new int[1 << (n - 1)];
        int[] t = new int[1 << (n - 1)];
        int id1 = 0, id2 = 0;
        boolean[] used = new boolean[1 << n];
        for (int i = 0, j = 0; i < (1 << n); i++) {
            if (used[i]) continue;
            s[id1++] = sums[i];
            used[i] = true;
            while (j < (1 << n) && (used[j] || sums[j] < sums[i] + delta)) j++;
            if (j < (1 << n) && sums[j] == sums[i] + delta) {
                t[id2++] = sums[j];
                used[j] = true;
            }
        }

        List<Integer> ans = dfs(n - 1, s);
        if (!ans.isEmpty()) {
            ans.add(delta);
            return ans;
        }

        ans = dfs(n - 1, t);
        if (!ans.isEmpty()) {
            ans.add(-delta);
            return ans;
        }

        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 总结

分析出几种情况，然后分别对各个情况实现

#Java