|
存在一个未知数组需要你进行还原，给你一个整数 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 == 2n
-104 <= sums[i] <= 104
参考：力扣
思路：本题来源于一个经典问题：已知子集的和求原子集并且已知原子集中所有的元素均为非负数。对于这个问题，我们很容易想到，将已知的子集的和从小到大排序，并且此时最小的值即为第一个元素，然后根据已知的元素，我们通过枚举子集的方式求出剩下的元素即可。
本题在原经典问题上进行了扩展，即原数组中存在负数，此时问题似乎变得难办了，我们应该考虑的是如何将该问题转化问原经典问题，使得问题得到解决。
为了满足原经典问题的约束条件，我们需要将保证原数组中所有负数组成的和，让其变为0，这样的话我们就能将子集的和转化为原数组中所有元素都为非负数时的和。这里读者可以思考一下。之后利用同样的解法即可。
class Solution {
public int[] recoverArray(int n, int[] sums) {
int mins = 0;
for (int x : sums)
mins = Math.min(mins, x);
mins = -mins;
Map<Integer, Integer> mp = new HashMap<>();
Map<Integer, Boolean> mp1 = new HashMap<>();
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> a - b);
for (int x : sums) {
q.add(x + mins);
mp.put(x + mins, mp.getOrDefault(x + mins, 0) + 1);
mp1.put(x + mins, false);
}
mp.put(q.peek(), mp.get(q.peek()) - 1);
q.poll(); //去掉空集合的值
int[] ans = new int[n];
ans[0] = q.poll();
for (int i = 1; i < n; i++) {
for (int msk = 0; msk < (1 << i); msk++) {
if (((msk >> (i - 1) & 1)) != 0) {
int sm = 0;
for (int j = 0; j < i; j++) {
if ((msk >> j & 1) != 0)
sm += ans[j];
}
mp.put(sm, mp.getOrDefault(sm, 0) - 1);
if (mp.get(sm) <= 0)
mp1.put(sm, true);
}
}
while (!q.isEmpty() && mp1.get(q.peek()))
q.poll();
ans[i] = q.peek();
}
for (int i = 0; i < (1 << n); i++) {
int sm = 0;
for (int j = 0; j < n; j++) {
if ((i >> j & 1) != 0)
sm += ans[j];
}
if (sm == mins) {
for (int j = 0; j < n; j++) {
if ((i >> j & 1) != 0)
ans[j] = -ans[j];
}
break;
}
}
return ans;
}
}
|