原文链接: https://leetcode-cn.com/problems/find-array-given-subset-sums
英文原文
You are given an integer n representing the length of an unknown array that you are trying to recover. You are also given an array sums containing the values of all 2n subset sums of the unknown array (in no particular order).
Return the array ans of length n representing the unknown array. If multiple answers exist, return any of them.
An array sub is a subset of an array arr if sub can be obtained from arr by deleting some (possibly zero or all) elements of arr. The sum of the elements in sub is one possible subset sum of arr. The sum of an empty array is considered to be 0.
Note: Test cases are generated such that there will always be at least one correct answer.
Example 1:
Input: n = 3, sums = [-3,-2,-1,0,0,1,2,3] Output: [1,2,-3] Explanation: [1,2,-3] is able to achieve the given subset sums: - []: sum is 0 - [1]: sum is 1 - [2]: sum is 2 - [1,2]: sum is 3 - [-3]: sum is -3 - [1,-3]: sum is -2 - [2,-3]: sum is -1 - [1,2,-3]: sum is 0 Note that any permutation of [1,2,-3] and also any permutation of [-1,-2,3] will also be accepted.
Example 2:
Input: n = 2, sums = [0,0,0,0] Output: [0,0] Explanation: The only correct answer is [0,0].
Example 3:
Input: n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8] Output: [0,-1,4,5] Explanation: [0,-1,4,5] is able to achieve the given subset sums.
Constraints:
1 <= n <= 15sums.length == 2n-104 <= sums[i] <= 104
中文题目
存在一个未知数组需要你进行还原，给你一个整数 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 <= 15sums.length == 2n-104 <= sums[i] <= 104
通过代码
高赞题解
本题的简化版（sums 中所有元素均为非负数）是一道非常经典的题目。本题在原题基础上进行了拓展，是一道兼具思考性和趣味性的好题。
所有元素均为非负数
该限制条件下可以用归纳法求解。在下述解法中，“从 multiset 里去除元素 $x$”指的是去除一个 $x$，而不是去除所有 $x$。
- 设 $\mathbb{S}$ 表示
sums中所有元素组成的 multiset。 - 首先将 $0$ 从 $\mathbb{S}$ 中去除，此时 $\mathbb{S}$ 中的最小值即为
ans中的最小值。 - 若我们已经推出了
ans中最小的 $k$ 个元素，那么我们从 $\mathbb{S}$ 中把这 $k$ 个元素所有子集的和去除。此时 $\mathbb{S}$ 中的最小值即为ans中的第 $(k + 1)$ 小值。
复杂度 $\mathcal{O}(2^nn)$。
所有元素可以为任意整数
解法
- 令 $m < 0$ 表示 $\mathbb{S}$ 中的最小值，将 $\mathbb{S}$ 中所有元素增加 $-m$ 变成另一个 multiset $\mathbb{S’}$。
- 对 $\mathbb{S’}$ 按
sums中所有元素均为非负数的方法求解，得到答案tmp。 - 寻找
tmp中的任意一个子集，使得该子集的和等于 $m$。把子集中的所有元素变为相反数（乘以 $-1$）后得到的ans即为最终答案。
复杂度仍为 复杂度 $\mathcal{O}(2^nn)$。
证明
令 $\mathbb{A}$ 表示“标准答案”的 multiset，令 $\mathbb{A}^-$ 表示 $\mathbb{A}$ 中所有负数组成的 multiset，显然有 $\sum \mathbb{A}^- = m$。
观察 $\mathbb{T} \subseteq \mathbb{A}$，可以发现 $\sum \mathbb{T} - m = \sum (\mathbb{T} \oplus \mathbb{A}^-)$，其中 $\oplus$ 是这样一种集合运算：若 $\mathbb{A}^-$ 中的一个元素 $a$ 也存在于 $\mathbb{T}$ 中，则将其从 $\mathbb{T}$ 中去除；否则将 $-a$ 加入 $\mathbb{T}$。因此原问题和转化后的问题的子集具有一一对应的映射关系，其中一个问题有解，另一个问题也有解。
代码
class Solution {
public:
vector<int> recoverArray(int n, vector<int>& sums) {
int BIAS = 0;
for (int x : sums) BIAS = min(BIAS, x);
BIAS = -BIAS;
multiset<int> st;
for (int x : sums) st.insert(x + BIAS);
st.erase(st.begin());
vector<int> ans;
ans.push_back(*st.begin());
for (int i = 1; i < n; i++) {
for (int msk = 0; msk < (1 << i); msk++) if (msk >> (i - 1) & 1) {
int sm = 0;
for (int j = 0; j < i; j++) if (msk >> j & 1) sm += ans[j];
st.erase(st.find(sm));
}
ans.push_back(*st.begin());
}
for (int i = 0; i < (1 << n); i++) {
int sm = 0;
for (int j = 0; j < n; j++) if (i >> j & 1) sm += ans[j];
if (sm == BIAS) {
for (int j = 0; j < n; j++) if (i >> j & 1) ans[j] = -ans[j];
break;
}
}
return ans;
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 887 | 1907 | 46.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
