Watch 6 video solutions for Find Array Given Subset Sums, a hard level problem involving Array, Divide and Conquer. This walkthrough by Happy Coding has 4,331 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 104Problem Overview: You are given all 2^n subset sums of an unknown integer array. The task is to reconstruct the original array. The sums include the empty subset and can contain negative values, which makes the reconstruction non-trivial.
Approach 1: Sorting and Iterative Extraction (Time: O(n·2^n), Space: O(2^n))
Start by sorting the subset sums. The smallest value always corresponds to the sum of the empty subset after normalization. The key observation: the difference between the two smallest remaining sums reveals one element of the original array. Once you discover this value x, split the current sums into two groups: sums without x and sums that include x. This is done using frequency counting while iterating through the sorted list. Remove the matched pairs and repeat the process until you recover all n elements. This method relies heavily on careful array manipulation and works well with sorted structures, making it a natural fit for problems involving array processing and subset construction.
Approach 2: Recursive Subset Sum Analysis (Time: O(n·2^n), Space: O(2^n))
This approach applies a divide and conquer strategy. After sorting the subset sums, compute the candidate element using the difference between the smallest two sums. Then recursively partition the sums into two halves: those formed without the element and those formed with it. The challenge is determining whether the candidate value is positive or negative. To resolve this, track which partition contains the zero sum (the empty subset). Recursively repeat the process on the correct half until the entire array is reconstructed. The recursion mirrors the structure of subset generation and systematically rebuilds the original values.
Recommended for interviews: The sorting and iterative extraction method is typically expected. It clearly demonstrates understanding of subset sum structure and efficient partitioning. The recursive divide-and-conquer version shows deeper insight and clean problem decomposition, which can impress interviewers if implemented correctly.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Iterative Extraction | O(n·2^n) | O(2^n) | Standard solution when reconstructing arrays from subset sums |
| Recursive Subset Sum Analysis | O(n·2^n) | O(2^n) | Useful when applying divide-and-conquer reasoning or recursive reconstruction |