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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1
2
3

Input: n = 2, sums = [0,0,0,0]
Output: [0,0]
Explanation: The only correct answer is [0,0].

Example 3

1
2
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 <= 15
  • sums.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

  1. Sort the sums array.
  2. For each step:
    • The smallest value in sums is 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.
  3. Repeat until all elements are found.

Code

 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

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;
    }
};
 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

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
}
 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

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();
    }
}
 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

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()
    }
}
 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

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
 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

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
    }
}
 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

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.