Find Array Given Subset Sums

Hard

#1806Time: 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.1 company

Algorithms

Divide and Conquer

Data structures

Array

Companies

Mindtickle

Prompt

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 2ⁿ 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 == 2ⁿ
-10⁴ <= sums[i] <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1// This is a conceptual illustration. A full implementation would be complex and inefficient.2class Solution {3    public int[] recoverArray(int n, int[] sums) {4        // The actual implementation would be very slow and likely time out.5        // It serves as a conceptual brute-force method.6        Map<Integer, Long> counts = new HashMap<>();7        for (int s : sums) {8            counts.put(s, counts.getOrDefault(s, 0L) + 1);9        }10 11        List<Integer> ans = new ArrayList<>();12        backtrack(n, counts, ans);13        return ans.stream().mapToInt(i -> i).toArray();14    }15 16    private boolean backtrack(int k, Map<Integer, Long> currentCounts, List<Integer> ans) {17        if (k == 0) {18            return currentCounts.size() == 1 && currentCounts.getOrDefault(0, 0L) > 0;19        }20 21        List<Integer> candidates = new ArrayList<>(currentCounts.keySet());22        for (int x : candidates) {23            if (x == 0) continue;24 25            Map<Integer, Long> nextCounts = tryPartition(currentCounts, x);26            if (nextCounts != null) {27                ans.add(x);28                if (backtrack(k - 1, nextCounts, ans)) {29                    return true;30                }31                ans.remove(ans.size() - 1); // Backtrack32            }33        }34        return false;35    }36 37    private Map<Integer, Long> tryPartition(Map<Integer, Long> counts, int d) {38        if (d == 0) return null;39        Map<Integer, Long> tempCounts = new HashMap<>(counts);40        Map<Integer, Long> nextCounts = new HashMap<>();41 42        List<Integer> sortedKeys = new ArrayList<>(tempCounts.keySet());43        Collections.sort(sortedKeys);44 45        for (int s : sortedKeys) {46            if (tempCounts.get(s) > 0) {47                long sCount = tempCounts.get(s);48                int partner = s + d;49                if (tempCounts.getOrDefault(partner, 0L) < sCount) {50                    return null; // Partition failed51                }52                tempCounts.put(s, 0L);53                tempCounts.put(partner, tempCounts.get(partner) - sCount);54                nextCounts.put(s, sCount);55            }56        }57        if (nextCounts.getOrDefault(0, 0L) == 0) return null;58        return nextCounts;59    }60}

Complexity

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.

Trade-offs

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

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.

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.
- 1. Sort the sums array.
- 1. Calculate the candidate difference d = sums[1] - sums[0].
- 1. Create a frequency map of the numbers in sums.
- 1. 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.
- 1. During the partition, check if 0 is placed into S1.
- 1. If 0 was placed in S1, the recovered element is d. The next sums array is S1.
- 1. Otherwise, the recovered element is -d. The next sums array is S2.
- 1. Add the recovered element to the answer array.
Return the final answer array.

Walkthrough

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:

Start with the full sums array and n.
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.
Repeat until all n elements are found.

1import java.util.*;2 3class Solution {4    public int[] recoverArray(int n, int[] sums) {5        Arrays.sort(sums);6        int[] ans = new int[n];7        int ansIdx = 0;8 9        for (int i = n; i > 0; i--) {10            int m = 1 << i;11            int d = sums[1] - sums[0];12            13            List<Integer> s1 = new ArrayList<>();14            List<Integer> s2 = new ArrayList<>();15            Map<Integer, Integer> counts = new HashMap<>();16            for (int s : sums) {17                counts.put(s, counts.getOrDefault(s, 0) + 1);18            }19 20            boolean zeroInS1 = false;21 22            for (int j = 0; j < m; j++) {23                int s = sums[j];24                if (counts.get(s) == 0) {25                    continue;26                }27 28                s1.add(s);29                counts.put(s, counts.get(s) - 1);30                31                int partner = s + d;32                s2.add(partner);33                counts.put(partner, counts.get(partner) - 1);34 35                if (s == 0) {36                    zeroInS1 = true;37                }38            }39 40            if (zeroInS1) {41                ans[ansIdx++] = d;42                sums = s1.stream().mapToInt(val -> val).toArray();43            } else {44                ans[ansIdx++] = -d;45                sums = s2.stream().mapToInt(val -> val).toArray();46            }47        }48        return ans;49    }50}

Complexity

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)`.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] recoverArray(int n, int[] sums) {4    int m = 1 << 30;5    for (int x : sums) {6      m = Math.min(m, x);7    }8    m = -m;9    TreeMap<Integer, Integer> tm = new TreeMap<>();10    for (int x : sums) {11      tm.merge(x + m, 1, Integer : : sum);12    }13    int[] ans = new int[n];14    if (tm.merge(0, -1, Integer : : sum) == 0) {15      tm.remove(0);16    }17    ans[0] = tm.firstKey();18    for (int i = 1; i < n; ++i) {19      for (int j = 0; j < 1 << i; ++j) {20        if ((j >> (i - 1) & 1) == 1) {21          int s = 0;22          for (int k = 0; k < i; ++k) {23            if (((j >> k) & 1) == 1) {24              s += ans[k];25            }26          }27          if (tm.merge(s, -1, Integer : : sum) == 0) {28            tm.remove(s);29          }30        }31      }32      ans[i] = tm.firstKey();33    }34    for (int i = 0; i < 1 << n; ++i) {35      int s = 0;36      for (int j = 0; j < n; ++j) {37        if (((i >> j) & 1) == 1) {38          s += ans[j];39        }40      }41      if (s == m) {42        for (int j = 0; j < n; ++j) {43          if (((i >> j) & 1) == 1) {44            ans[j] *= -1;45          }46        }47        break;48      }49    }50    return ans;51  }52}

1class Solution {2public:3  vector<int> recoverArray(int n, vector<int> &sums) {4    int m = *min_element(sums.begin(), sums.end());5    m = -m;6    multiset<int> st;7    for (int x : sums) {8      st.insert(x + m);9    }10    st.erase(st.begin());11    vector<int> ans;12    ans.push_back(*st.begin());13    for (int i = 1; i < n; ++i) {14      for (int j = 0; j < 1 << i; ++j) {15        if (j >> (i - 1) & 1) {16          int s = 0;17          for (int k = 0; k < i; ++k) {18            if (j >> k & 1) {19              s += ans[k];20            }21          }22          st.erase(st.find(s));23        }24      }25      ans.push_back(*st.begin());26    }27    for (int i = 0; i < 1 << n; ++i) {28      int s = 0;29      for (int j = 0; j < n; ++j) {30        if (i >> j & 1) {31          s += ans[j];32        }33      }34      if (s == m) {35        for (int j = 0; j < n; ++j) {36          if (i >> j & 1) {37            ans[j] = -ans[j];38          }39        }40        break;41      }42    }43    return ans;44  }45};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem