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.
Begin by sorting the array of subset sums. The idea is to iteratively extract elements of the unknown array. Start by picking the smallest possible subset, noting that a subset sum 0 should exist for the empty set. Each extracted element allows you to partition the remaining subset sums. Given the smallest subset sums involve an element a, you can infer which sums involve a by revisiting combinations. Adjust the list accordingly to remove identified sums, and attempt to extract one element at a time from the remaining set of sums.
This solution works by sorting the subset sums and iteratively deducing one element of the array at a time. We make use of the fact that the smallest element in the sorted list is used to deduce one element (the minimum one) of the original array. By tracking counts of remaining sums reduced by this value, we can reconstruct the remaining subset sums iteratively.
Time Complexity: O(m log m + m) where m = 2^n. We start by sorting the sums and then iteratively process them.
Space Complexity: O(m) because of the storage required for remaining sums.
Another alternative approach involves recursion to decode the subset sums, applying logical deductions repeatedly until all elements of the array are determined. Each recursive call considers the smallest subset sum, determines potential contributions by a candidate element, and partitions subset sums accordingly. This method effectively narrows down the elements by recursive elimination and substitution.
Utilizing a recursive approach means breaking down the subset sums iteratively by element deduction. We recurrently determine the difference implied by smallest elements in subsets, reduce the subset, and recoursively seek additional array elements until all deduced values combine into the original array.
Time Complexity: O(m log m), where m = 2^n, primarily due to repeated sorting and recursive management of subset sums.
Space Complexity: O(m) for recursion stack and intermediate results.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Iterative Extraction | Time Complexity: O(m log m + m) where m = 2^n. We start by sorting the sums and then iteratively process them. |
| Approach 2: Recursive Subset Sum Analysis | Time Complexity: O(m log m), where m = 2^n, primarily due to repeated sorting and recursive management of subset sums. |
| Default Approach | — |
| 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 |
LeetCode 1982. Find Array Given Subset Sums • Happy Coding • 4,331 views views
Watch 5 more video solutions →Practice Find Array Given Subset Sums with our built-in code editor and test cases.
Practice on FleetCode