# Find Array Given Subset Sums
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-array-given-subset-sums)
Canonical: https://scaleengineer.com/dsa/problems/find-array-given-subset-sums
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array
**Companies:** [Mindtickle](https://scaleengineer.com/companies/mindtickle)
---
## 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 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 <= 15`
* `sums.length == 2n`
* `-104 <= sums[i] <= 104`

# Approaches
## Backtracking Search
This approach attempts to find the unknown array by trying all possibilities for its elements in a recursive, backtracking manner. It explores a search tree where each level corresponds to determining one element of the array.
**Time:** Worst-case is exponential in `n` and the number of unique sums. The branching factor at each of the `n` levels of recursion can be up to `O(2^n)`, leading to a complexity far exceeding practical limits, something like `O((2^n)! * 2^n)`. · **Space:** O(n * 2^n) due to the recursion stack, where at each level a copy of the frequency map of sums (of size up to `2^n`) is stored.
**Pros:** Conceptually simple to understand as it explores all possibilities.
**Cons:** Extremely inefficient due to the large branching factor.; Will time out for the given constraints (`n` up to 15).
### Explanation
The core idea is to build the solution array element by element. We define a recursive function, say `find(k, current_sums)`, which tries to find the remaining `k` elements given the `current_sums` that they must generate.

In each call, we iterate through all unique, non-zero values `x` in `current_sums` as a candidate for the next element. For each candidate `x`, we check if `current_sums` can be partitioned into two sets, `S` and `S+x`. If a valid partition exists (where `S` is a valid set of subset sums, meaning it contains 0), we add `x` to our potential answer and recurse with `find(k-1, S)`. If the recursive call eventually succeeds, we have found a solution. If not, or if a valid partition for `x` cannot be found, we backtrack by removing `x` and trying the next candidate.

The base case for the recursion is when `k=0`. If `current_sums` is `[0]`, it means we have successfully explained all sums, and a valid array has been found.

```java
// This is a conceptual illustration. A full implementation would be complex and inefficient.
class Solution {
    public int[] recoverArray(int n, int[] sums) {
        // The actual implementation would be very slow and likely time out.
        // It serves as a conceptual brute-force method.
        Map<Integer, Long> counts = new HashMap<>();
        for (int s : sums) {
            counts.put(s, counts.getOrDefault(s, 0L) + 1);
        }

        List<Integer> ans = new ArrayList<>();
        backtrack(n, counts, ans);
        return ans.stream().mapToInt(i -> i).toArray();
    }

    private boolean backtrack(int k, Map<Integer, Long> currentCounts, List<Integer> ans) {
        if (k == 0) {
            return currentCounts.size() == 1 && currentCounts.getOrDefault(0, 0L) > 0;
        }

        List<Integer> candidates = new ArrayList<>(currentCounts.keySet());
        for (int x : candidates) {
            if (x == 0) continue;

            Map<Integer, Long> nextCounts = tryPartition(currentCounts, x);
            if (nextCounts != null) {
                ans.add(x);
                if (backtrack(k - 1, nextCounts, ans)) {
                    return true;
                }
                ans.remove(ans.size() - 1); // Backtrack
            }
        }
        return false;
    }

    private Map<Integer, Long> tryPartition(Map<Integer, Long> counts, int d) {
        if (d == 0) return null;
        Map<Integer, Long> tempCounts = new HashMap<>(counts);
        Map<Integer, Long> nextCounts = new HashMap<>();

        List<Integer> sortedKeys = new ArrayList<>(tempCounts.keySet());
        Collections.sort(sortedKeys);

        for (int s : sortedKeys) {
            if (tempCounts.get(s) > 0) {
                long sCount = tempCounts.get(s);
                int partner = s + d;
                if (tempCounts.getOrDefault(partner, 0L) < sCount) {
                    return null; // Partition failed
                }
                tempCounts.put(s, 0L);
                tempCounts.put(partner, tempCounts.get(partner) - sCount);
                nextCounts.put(s, sCount);
            }
        }
        if (nextCounts.getOrDefault(0, 0L) == 0) return null;
        return nextCounts;
    }
}
```
### Algorithm
- Define a recursive function `backtrack(k, sums_map)` that attempts to find `k` elements.
- The base case is `k=0`. If `sums_map` contains only `{0: 1}`, a solution is found.
- In the recursive step, iterate through all unique values `x` in the current `sums_map` as candidates for an element.
- For each candidate `x`, attempt to partition the current sums into a new set of sums `S` and `S+x`.
- If a valid partition is found (i.e., `S` contains 0 and all sums are accounted for), add `x` to the result and recurse: `backtrack(k-1, S)`.
- If the recursive call returns true, propagate the success. Otherwise, backtrack by removing `x` and trying the next candidate.

## Recursive Decomposition with Difference Candidate
This efficient approach leverages a key insight into the structure of subset sums. By identifying one element `x` of the unknown array, the problem can be reduced to finding an array of size `n-1` from a new set of sums half the size. A strong candidate for `x` can be found by observing the smallest sums.
**Time:** O(n * 2^n). The main loop runs `n` times. Inside the loop, for a sums array of size `m`, we sort (`O(m log m)`) and partition (`O(m)`). The total complexity is the sum of `O(2^k * k)` for `k` from `1` to `n`, which is dominated by the largest term, resulting in `O(n * 2^n)`. · **Space:** O(2^n). We need space to store the current `sums` array, the frequency map, and the two new lists `S1` and `S2` during partitioning. The space requirement halves at each step, so the peak usage is `O(2^n)`.
**Pros:** Highly efficient and guaranteed to find a correct solution.; The logic is deterministic, avoiding a large search space.
**Cons:** The core insight (`d = sums[1] - sums[0]`) is not immediately obvious.; Requires careful implementation of the partitioning logic.
### Explanation
Let `Sums_n` be the set of `2^n` subset sums. If we know one element `x`, then `Sums_n` is the union of `Sums_{n-1}` (subset sums of the other `n-1` elements) and `Sums_{n-1} + x` (each sum from `Sums_{n-1}` increased by `x`).

This structure allows for a recursive solution. The main challenge is to find an element `x`. If we sort `Sums_n`, the difference `d = sums[1] - sums[0]` becomes a powerful candidate. It can be shown that either `d` or `-d` must be one of the elements in the unknown array.

The algorithm is as follows:
1. Start with the full `sums` array and `n`.
2. In a loop that runs `n` times (or a recursive function):
   a. Let the current number of elements to find be `k` and the array of sums be `current_sums` (size `2^k`).
   b. Sort `current_sums`.
   c. Calculate the difference `d = current_sums[1] - current_sums[0]`.
   d. Greedily partition `current_sums` into two lists, `S1` and `S2`, of size `2^(k-1)`. Iterate through the sorted `current_sums`; for each number `s`, pair it with `s+d`. This is done efficiently with a frequency map.
   e. After partitioning, one list represents `Sums_{k-1}` and the other `Sums_{k-1} + x`. The `Sums_{k-1}` set must contain `0` (for the empty subset). We check which list, `S1` or `S2`, contains `0`.
   f. If `S1` contains `0`, then the element is `d`, and `S1` is the new set of sums for the `k-1` problem.
   g. If `S2` contains `0`, then the element is `-d`, and `S2` is the new set of sums.
   h. Add the found element to the result and continue with the new, smaller set of sums.
3. Repeat until all `n` elements are found.

```java
import java.util.*;

class Solution {
    public int[] recoverArray(int n, int[] sums) {
        Arrays.sort(sums);
        int[] ans = new int[n];
        int ansIdx = 0;

        for (int i = n; i > 0; i--) {
            int m = 1 << i;
            int d = sums[1] - sums[0];
            
            List<Integer> s1 = new ArrayList<>();
            List<Integer> s2 = new ArrayList<>();
            Map<Integer, Integer> counts = new HashMap<>();
            for (int s : sums) {
                counts.put(s, counts.getOrDefault(s, 0) + 1);
            }

            boolean zeroInS1 = false;

            for (int j = 0; j < m; j++) {
                int s = sums[j];
                if (counts.get(s) == 0) {
                    continue;
                }

                s1.add(s);
                counts.put(s, counts.get(s) - 1);
                
                int partner = s + d;
                s2.add(partner);
                counts.put(partner, counts.get(partner) - 1);

                if (s == 0) {
                    zeroInS1 = true;
                }
            }

            if (zeroInS1) {
                ans[ansIdx++] = d;
                sums = s1.stream().mapToInt(val -> val).toArray();
            } else {
                ans[ansIdx++] = -d;
                sums = s2.stream().mapToInt(val -> val).toArray();
            }
        }
        return ans;
    }
}
```
### Algorithm
- Start with the given `n` and `sums`.
- Repeat `n` times to find each element:
  - 1. Let the current size of the `sums` array be `m = 2^k`.
  - 2. Sort the `sums` array.
  - 3. Calculate the candidate difference `d = sums[1] - sums[0]`.
  - 4. Create a frequency map of the numbers in `sums`.
  - 5. Greedily partition `sums` into two new lists, `S1` and `S2`. Iterate through `sums`; for each element `s` not yet used, add `s` to `S1`, `s+d` to `S2`, and decrement their counts in the map.
  - 6. During the partition, check if `0` is placed into `S1`.
  - 7. If `0` was placed in `S1`, the recovered element is `d`. The next `sums` array is `S1`.
  - 8. Otherwise, the recovered element is `-d`. The next `sums` array is `S2`.
  - 9. Add the recovered element to the answer array.
- Return the final answer array.

# Solutions
### Java

```java
class Solution {
public
  int[] recoverArray(int n, int[] sums) {
    int m = 1 << 30;
    for (int x : sums) {
      m = Math.min(m, x);
    }
    m = -m;
    TreeMap<Integer, Integer> tm = new TreeMap<>();
    for (int x : sums) {
      tm.merge(x + m, 1, Integer : : sum);
    }
    int[] ans = new int[n];
    if (tm.merge(0, -1, Integer : : sum) == 0) {
      tm.remove(0);
    }
    ans[0] = tm.firstKey();
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j < 1 << i; ++j) {
        if ((j >> (i - 1) & 1) == 1) {
          int s = 0;
          for (int k = 0; k < i; ++k) {
            if (((j >> k) & 1) == 1) {
              s += ans[k];
            }
          }
          if (tm.merge(s, -1, Integer : : sum) == 0) {
            tm.remove(s);
          }
        }
      }
      ans[i] = tm.firstKey();
    }
    for (int i = 0; i < 1 << n; ++i) {
      int s = 0;
      for (int j = 0; j < n; ++j) {
        if (((i >> j) & 1) == 1) {
          s += ans[j];
        }
      }
      if (s == m) {
        for (int j = 0; j < n; ++j) {
          if (((i >> j) & 1) == 1) {
            ans[j] *= -1;
          }
        }
        break;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> recoverArray(int n, vector<int> &sums) {
    int m = *min_element(sums.begin(), sums.end());
    m = -m;
    multiset<int> st;
    for (int x : sums) {
      st.insert(x + m);
    }
    st.erase(st.begin());
    vector<int> ans;
    ans.push_back(*st.begin());
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j < 1 << i; ++j) {
        if (j >> (i - 1) & 1) {
          int s = 0;
          for (int k = 0; k < i; ++k) {
            if (j >> k & 1) {
              s += ans[k];
            }
          }
          st.erase(st.find(s));
        }
      }
      ans.push_back(*st.begin());
    }
    for (int i = 0; i < 1 << n; ++i) {
      int s = 0;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          s += ans[j];
        }
      }
      if (s == m) {
        for (int j = 0; j < n; ++j) {
          if (i >> j & 1) {
            ans[j] = -ans[j];
          }
        }
        break;
      }
    }
    return ans;
  }
};

```

### Python

```python
from sortedcontainers import SortedList class Solution : def recoverArray ( self , n : int , sums : List [ int ]) -> List [ int ]: m = - min ( sums ) sl = SortedList ( x + m for x in sums ) sl . remove ( 0 ) ans = [ sl [ 0 ]] for i in range ( 1 , n ): for j in range ( 1 << i ): if j >> ( i - 1 ) & 1 : s = sum ( ans [ k ] for k in range ( i ) if j >> k & 1 ) sl . remove ( s ) ans . append ( sl [ 0 ]) for i in range ( 1 << n ): s = sum ( ans [ j ] for j in range ( n ) if i >> j & 1 ) if s == m : for j in range ( n ): if i >> j & 1 : ans [ j ] *= - 1 break return ans
```