Skip to main content
Talentd

Find Array Given Subset Sums - Solution & Explanation

HardArrayDivide and Conquer10 min readAsked at: Mindtickle
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Approach 1: Sorting and Iterative Extraction

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.

Code

PythonC++Java

Python

C++

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Recursive Subset Sum Analysis

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(m) because of the storage required for remaining sums.

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.
Space Complexity: O(m) for recursion stack and intermediate results.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Iterative ExtractionO(n·2^n)O(2^n)Standard solution when reconstructing arrays from subset sums
Recursive Subset Sum AnalysisO(n·2^n)O(2^n)Useful when applying divide-and-conquer reasoning or recursive reconstruction

Video Solution

LeetCode 1982. Find Array Given Subset Sums • Happy Coding • 4,468 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Find Array Given Subset Sums easy or hard?
Find Array Given Subset Sums is classified as a Hard problem. The difficulty comes from recognizing the structure of subset sums and correctly partitioning them during reconstruction, especially when negative numbers are involved.
Find Array Given Subset Sums Python or Java solution?
Python, Java, and C++ implementations typically follow the same algorithm: sort the subset sums, compute the candidate element, and partition sums using a frequency structure. Each iteration extracts one element of the original array until all values are recovered.
How to solve Find Array Given Subset Sums efficiently?
Sort the subset sums and repeatedly determine the next array element from the difference between the smallest values. Use a frequency map or multiset to split sums into two groups: those containing the element and those without it. Continue until all elements are reconstructed. The resulting complexity is O(n·2^n).
What is the best approach for Find Array Given Subset Sums?
The most common approach sorts the subset sums and iteratively extracts elements of the original array. By observing that the difference between the smallest sums reveals a new element, you can partition sums into groups with and without that element. This method runs in O(n·2^n) time and is the expected solution in interviews.
What data structure is used in Find Array Given Subset Sums?
The solution primarily uses arrays along with auxiliary structures such as hash maps, counters, or multisets to track frequencies of subset sums. Sorting is essential, and efficient grouping of sums is required to reconstruct the original array.
What is the time complexity of Find Array Given Subset Sums?
The typical solution runs in O(n·2^n) time because the algorithm processes all subset sums at each step while extracting n elements. Sorting the sums initially costs O(2^n log 2^n), and the repeated grouping operations dominate the runtime. Space complexity is O(2^n) to store and manipulate the subset sums.
Is Find Array Given Subset Sums asked at Google, Amazon, or Meta?
Problems involving subset reconstruction and divide-and-conquer reasoning appear in interviews at companies like Google and Meta. While this exact problem may not always appear verbatim, similar subset sum and reconstruction challenges are common in high-level algorithm interviews.

Ready to solve this problem?

Practice Find Array Given Subset Sums with our built-in code editor and test cases.

Practice on FleetCode
Previous

Recover the Original Array

Next

Subsets