Find Array Given Subset Sums
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 arrayans of lengthn representing the unknown array.
Ifmultiple 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.
Examples
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-10^4 <= sums[i] <= 10^4
Solution
Method 1 – Multiset and Divide and Conquer
Intuition
The smallest subset sum is always 0 (empty set). The next smallest subset sum must be the smallest element in the array (or its negative if the array contains negatives). We can recursively extract the smallest element, partition the subset sums into those that include it and those that do not, and repeat for the rest of the array.
Approach
- Sort the
sumsarray. - For each step:
- The smallest value in
sumsis always 0. - The next smallest difference is the smallest element (could be negative).
- Partition the subset sums into two groups: those with and without the current element.
- Use a multiset (Counter) to efficiently remove pairs.
- Recursively solve for the rest of the array.
- The smallest value in
- Repeat until all elements are found.
Code
C++
class Solution {
public:
vector<int> recoverArray(int n, vector<int>& sums) {
multiset<int> ms(sums.begin(), sums.end());
vector<int> ans;
while (n--) {
int x = *next(ms.begin());
int d = x - *ms.begin();
multiset<int> left, right;
map<int, int> cnt;
for (int v : ms) cnt[v]++;
for (int v : ms) {
if (cnt[v] == 0) continue;
left.insert(v);
cnt[v]--;
cnt[v + d]--;
}
if (left.size() < ms.size() / 2) d = -d;
ans.push_back(d);
multiset<int> nextms;
cnt.clear();
for (int v : ms) cnt[v]++;
for (int v : ms) {
if (cnt[v] == 0) continue;
cnt[v]--;
cnt[v + d]--;
nextms.insert(v);
}
ms = nextms;
}
return ans;
}
};
Go
func recoverArray(n int, sums []int) []int {
sort.Ints(sums)
ans := []int{}
for n > 0 {
d := sums[1] - sums[0]
cnt := map[int]int{}
for _, v := range sums { cnt[v]++ }
left := []int{}
for _, v := range sums {
if cnt[v] == 0 { continue }
left = append(left, v)
cnt[v]--
cnt[v+d]--
}
if len(left) < len(sums)/2 { d = -d }
ans = append(ans, d)
cnt = map[int]int{}
for _, v := range sums { cnt[v]++ }
nextsums := []int{}
for _, v := range sums {
if cnt[v] == 0 { continue }
cnt[v]--
cnt[v+d]--
nextsums = append(nextsums, v)
}
sums = nextsums
n--
}
return ans
}
Java
class Solution {
public int[] recoverArray(int n, int[] sums) {
Arrays.sort(sums);
List<Integer> ans = new ArrayList<>();
while (n-- > 0) {
int d = sums[1] - sums[0];
Map<Integer, Integer> cnt = new HashMap<>();
for (int v : sums) cnt.put(v, cnt.getOrDefault(v, 0) + 1);
List<Integer> left = new ArrayList<>();
for (int v : sums) {
if (cnt.get(v) == 0) continue;
left.add(v);
cnt.put(v, cnt.get(v) - 1);
cnt.put(v + d, cnt.get(v + d) - 1);
}
if (left.size() < sums.length / 2) d = -d;
ans.add(d);
cnt.clear();
for (int v : sums) cnt.put(v, cnt.getOrDefault(v, 0) + 1);
List<Integer> nextsums = new ArrayList<>();
for (int v : sums) {
if (cnt.get(v) == 0) continue;
cnt.put(v, cnt.get(v) - 1);
cnt.put(v + d, cnt.get(v + d) - 1);
nextsums.add(v);
}
sums = nextsums.stream().mapToInt(i->i).toArray();
}
return ans.stream().mapToInt(i->i).toArray();
}
}
Kotlin
class Solution {
fun recoverArray(n: Int, sums: IntArray): IntArray {
sums.sort()
val ans = mutableListOf<Int>()
var m = n
var s = sums.toList()
while (m-- > 0) {
val d = s[1] - s[0]
val cnt = mutableMapOf<Int, Int>()
for (v in s) cnt[v] = cnt.getOrDefault(v, 0) + 1
val left = mutableListOf<Int>()
for (v in s) {
if (cnt[v] == 0) continue
left.add(v)
cnt[v] = cnt[v]!! - 1
cnt[v + d] = cnt.getOrDefault(v + d, 0) - 1
}
val reald = if (left.size < s.size / 2) -d else d
ans.add(reald)
val cnt2 = mutableMapOf<Int, Int>()
for (v in s) cnt2[v] = cnt2.getOrDefault(v, 0) + 1
val nexts = mutableListOf<Int>()
for (v in s) {
if (cnt2[v] == 0) continue
cnt2[v] = cnt2[v]!! - 1
cnt2[v + reald] = cnt2.getOrDefault(v + reald, 0) - 1
nexts.add(v)
}
s = nexts
}
return ans.toIntArray()
}
}
Python
class Solution:
def recoverArray(self, n: int, sums: list[int]) -> list[int]:
from collections import Counter
sums.sort()
ans = []
for _ in range(n):
d = sums[1] - sums[0]
cnt = Counter(sums)
left = []
for v in sums:
if cnt[v] == 0:
continue
left.append(v)
cnt[v] -= 1
cnt[v + d] -= 1
if len(left) < len(sums) // 2:
d = -d
ans.append(d)
cnt = Counter(sums)
nextsums = []
for v in sums:
if cnt[v] == 0:
continue
cnt[v] -= 1
cnt[v + d] -= 1
nextsums.append(v)
sums = nextsums
return ans
Rust
use std::collections::HashMap;
impl Solution {
pub fn recover_array(n: i32, mut sums: Vec<i32>) -> Vec<i32> {
sums.sort();
let mut ans = vec![];
let mut m = n;
while m > 0 {
let d = sums[1] - sums[0];
let mut cnt = HashMap::new();
for &v in &sums { *cnt.entry(v).or_insert(0) += 1; }
let mut left = vec![];
for &v in &sums {
if *cnt.get(&v).unwrap_or(&0) == 0 { continue; }
left.push(v);
*cnt.get_mut(&v).unwrap() -= 1;
*cnt.entry(v + d).or_insert(0) -= 1;
}
let reald = if left.len() < sums.len() / 2 { -d } else { d };
ans.push(reald);
let mut cnt2 = HashMap::new();
for &v in &sums { *cnt2.entry(v).or_insert(0) += 1; }
let mut nexts = vec![];
for &v in &sums {
if *cnt2.get(&v).unwrap_or(&0) == 0 { continue; }
*cnt2.get_mut(&v).unwrap() -= 1;
*cnt2.entry(v + reald).or_insert(0) -= 1;
nexts.push(v);
}
sums = nexts;
m -= 1;
}
ans
}
}
TypeScript
class Solution {
recoverArray(n: number, sums: number[]): number[] {
sums.sort((a, b) => a - b);
const ans: number[] = [];
for (let m = n; m > 0; m--) {
let d = sums[1] - sums[0];
const cnt = new Map<number, number>();
for (const v of sums) cnt.set(v, (cnt.get(v) ?? 0) + 1);
const left: number[] = [];
for (const v of sums) {
if ((cnt.get(v) ?? 0) === 0) continue;
left.push(v);
cnt.set(v, (cnt.get(v) ?? 0) - 1);
cnt.set(v + d, (cnt.get(v + d) ?? 0) - 1);
}
if (left.length < sums.length / 2) d = -d;
ans.push(d);
const cnt2 = new Map<number, number>();
for (const v of sums) cnt2.set(v, (cnt2.get(v) ?? 0) + 1);
const nexts: number[] = [];
for (const v of sums) {
if ((cnt2.get(v) ?? 0) === 0) continue;
cnt2.set(v, (cnt2.get(v) ?? 0) - 1);
cnt2.set(v + d, (cnt2.get(v + d) ?? 0) - 1);
nexts.push(v);
}
sums = nexts;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * 2^n), as each step processes all subset sums. - 🧺 Space complexity:
O(2^n), for storing the subset sums and counters.