1982. Find Array Given Subset Sums
Problem Description
You are given a task to determine an unknown array of length n
. An array sums
, which holds all 2^n
subset sums of the unknown array, is provided, but the order of these sums is not given. A subset sum is the sum of a subset of the elements of the array, where a subset can be any combination of elements, including the empty set (which sums to 0
).
The goal is to return any version of the unknown array of length n
that matches the subset sums provided in sums
. There may be multiple valid solutions, and any one of them would be an acceptable answer.
Key Concepts:
- Subset Sums: The sum of elements of a possible subset of the array.
- Unknown Array: The original array we aim to find, which has
n
elements. - All Possible Subsets: For an array of
n
elements,2^n
subsets exist.
The problem assures us that at least one correct answer will always be achievable with the given input.
Intuition
To retrieve the original array from the subset sums, we can leverage the following insights:
-
The smallest value in the
sums
array must be the sum of an empty subset, thus it should be0
. If not, that implies that all subsets include a negative number, which is also the minimum value of the original array. -
Once we identify the minimum subset sum (which could be negative), we can adjust all other subset sums accordingly. In adjusting, we hypothetically add a value to each subset sum to transform the minimum value to 0.
-
As we adjust the subset values, we start building the possible original array. To do this, we remove the sum equivalent to the already identified elements of the array from the
sums
list. -
We repeat this process recursively, deducing one array element at a time and removing the matching sums, until we have derived all elements of the array.
-
Finally, we need to check if the array we built requires an adjustment due to our initial addition transformation to ensure that the minimum subset calculation started from 0. If we made this change at the beginning, we need to convert all elements that contributed to creating the negative subset sums back to their original (negative) values.
This intuition utilizes a strategy like a reverse engineering process of the subset sums to build up the potential original array, one element at a time.
Learn more about Divide and Conquer patterns.
Solution Approach
The implementation steps follow the intuition closely, applying algorithmic thinking and making use of a data structure called SortedList
from the sortedcontainers
module in Python. SortedList
provides a variety of efficient list operations including insertions, removals, and lookups.
Here's a step-by-step walkthrough of the implementation inspired by the provided code snippet:
-
Initialize Adjustments: The minimum value in the
sums
list is determined, which should represent the sum of the empty subset and hence should be zero. If it's not zero, it indicates the presence of negative numbers in the unknown array. This minimum value is subtracted from all elements insums
to "re-adjust" the subset sums as if they were calculated with the original array having no negatives. ASortedList
is used forsums
with the re-adjusted values. -
Start Building the Array: The first element in the sorted
sums
list after the adjustment is always zero due to the empty subset. This zero value is removed, and the next smallest value is taken as the first element of the original array (ans[0]
). -
Iterative Process: For each additional element
i
in the array, a nested loop is used. It traverses all the subset combinations found so far and removes the corresponding subset sum fromsums
list. This works because, with each new element ofans
, you form new subsets that combine the new element with all previous subsets. -
Removing Subset Sums: A bit manipulation technique is employed to determine which elements of
ans
contribute to each subset sum. An inner loop calculates the subset sums
for a given subset indicated byj
(binary representation ofj
indicates which elements to include), and thens
is removed from the sorted list. -
Restoring Negative Elements: After the final loop, some elements in
ans
might be the adjusted positive counterparts of negative numbers in the original array. The array is traversed one last time to find the combination of elements that sums up to the negative of the minimum value (m
). These elements are identified by a bitmask comparison. If the corresponding bit is set, this means the element was part of the subset that created the negative minimum value, and thus it is multiplied by-1
to restore its original (negative) value.
Throughout the implementation, bitwise operations are extensively used to iterate through all possible subset combinations. The initial detection and potential re-adjustment of negative values are crucial. The use of SortedList
allows for efficient management of the subset sums, which otherwise would have been computationally intensive to maintain in sorted order.
This approach is effective in decoding the subset sums to reconstruct the original array but requires clever manipulation and close attention to the way bits represent subsets.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example using a small unknown array.
Suppose we are given the following subset sums for an unknown array of length n=2
: sums = [0, 1, 1, 2]
. These sums represent all possible subsets of the unknown array.
Following the steps outlined in the solution approach:
-
Initialize Adjustments: We begin by identifying the minimum element in the subset sums, which should be
0
. In this example, the smallest value is indeed0
, so there's no need to adjust thesums
array for negative numbers. -
Start Building the Array: We remove the first element which is
0
from the sortedsums
, since this corresponds to the empty subset. The next smallest value is1
, which we take as the first element of the original array (ans[0] = 1
). -
Iterative Process: To find the next element, we remove subset sums that already include our first element.
- Since we know
ans[0] = 1
, the subset sums that include this element would also be1
(fromans[0]
itself) and2
(which includesans[0]
and the unknown second element). - We remove
1
and2
from thesums
array, and we are left with[1]
.
- Since we know
-
Removing Subset Sums: What remains in the
sums
is the value of the second element of the array (ans[1]
). Since the only left value insums
is1
, we deduce thatans[1] = 1
. -
Restoring Negative Elements: In our case, no negative adjustments were made in the first step, so we do not need to convert any values back to negative.
So, the original array ans
that corresponds to the given subset sums [0, 1, 1, 2]
is [1, 1]
.
It is important to note that this is just one example to demonstrate the steps. The solution approach can handle larger arrays and more complex scenarios, including those with negative numbers and larger subset sums. The key lies in systematically using sorted lists to manage and remove subset sums to reveal the original array's elements.
Solution Implementation
1from sortedcontainers import SortedList
2
3class Solution:
4 def recoverArray(self, n: int, sums: List[int]) -> List[int]:
5 # Find the negative of the minimum sum, which is the offset to be added
6 offset = -min(sums)
7
8 # Create a SortedList from the sums after adjusting each element by the calculated offset
9 sorted_list = SortedList(x + offset for x in sums)
10 # Remove the zero that must exist since one subset is the empty set
11 sorted_list.remove(0)
12
13 # Initialize an array to hold the answer elements
14 answer = [sorted_list[0]]
15
16 # Iterate through 1 to n - 1 to find each number in the original array
17 for i in range(1, n):
18 # Try every possible combination of numbers found so far
19 for j in range(1 << i):
20 # Check if the ith bit is set in the binary representation of j
21 if j >> (i - 1) & 1:
22 # Calculate the sum for the current combination
23 combination_sum = sum(answer[k] for k in range(i) if j >> k & 1)
24 # Remove the calculated sum from the sorted list
25 sorted_list.remove(combination_sum)
26 # The smallest number left is the next number in the answer
27 answer.append(sorted_list[0])
28
29 # Look for the subset in the answer that adds up to the offset
30 for i in range(1 << n):
31 subset_sum = sum(answer[j] for j in range(n) if i >> j & 1)
32 # If the subset sum matches the offset, it means the corresponding subset
33 # came from negations in original array, so we need to negate them back
34 if subset_sum == offset:
35 for j in range(n):
36 if i >> j & 1:
37 answer[j] *= -1
38 break
39
40 # Return the recovered original array, which now contains correct signs
41 return answer
42
1import java.util.TreeMap;
2
3class Solution {
4 public int[] recoverArray(int n, int[] sums) {
5 // Find the minimum value in sums array to determine the offset
6 int minSumValue = Integer.MAX_VALUE;
7 for (int sum : sums) {
8 minSumValue = Math.min(minSumValue, sum);
9 }
10 int offset = -minSumValue; // offset to be added to each element in sums
11
12 // Create a TreeMap to store the frequency of each sum + offset
13 TreeMap<Integer, Integer> frequencyMap = new TreeMap<>();
14 for (int sum : sums) {
15 // Merging and adding offset to each value (ensuring duplicates are accounted for)
16 frequencyMap.merge(sum + offset, 1, Integer::sum);
17 }
18
19 // Initialize the array to hold the answer
20 int[] answer = new int[n];
21 if (frequencyMap.merge(0, -1, Integer::sum) == 0) {
22 // Remove the entry if the frequency drops to zero after decrementing
23 frequencyMap.remove(0);
24 }
25 answer[0] = frequencyMap.firstKey(); // Take the smallest element after offset as the first element of the answer
26
27 // Build up the answer by determining each subsequent element
28 for (int i = 1; i < n; ++i) {
29 for (int j = 0; j < 1 << i; ++j) {
30 if ((j >> (i - 1) & 1) == 1) {
31 int sumSubset = 0;
32 // Calculate sum of a subset of answer array determined by bits of j
33 for (int k = 0; k < i; ++k) {
34 if (((j >> k) & 1) == 1) {
35 sumSubset += answer[k];
36 }
37 }
38 // Decrement frequency and potentially remove the entry
39 if (frequencyMap.merge(sumSubset, -1, Integer::sum) == 0) {
40 frequencyMap.remove(sumSubset);
41 }
42 }
43 }
44 // Set the next element of answer as the smallest key remaining in frequencyMap
45 answer[i] = frequencyMap.firstKey();
46 }
47
48 // Check if the sums include an array that sums up to offset
49 // If so, their negations are part of the correct answer
50 for (int i = 0; i < 1 << n; ++i) {
51 int subsetSum = 0;
52 for (int j = 0; j < n; ++j) {
53 if (((i >> j) & 1) == 1) {
54 subsetSum += answer[j];
55 }
56 }
57 if (subsetSum == offset) {
58 // Invert the sign for elements which were part of the subset adding up to offset
59 for (int j = 0; j < n; ++j) {
60 if (((i >> j) & 1) == 1) {
61 answer[j] *= -1;
62 }
63 }
64 break; // The correct answer is found, so we break out of the loop
65 }
66 }
67
68 // Return the recovered array
69 return answer;
70 }
71}
72
1#include <vector>
2#include <set>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> recoverArray(int n, vector<int>& sums) {
10 // Find the minimum element in `sums` and negate it to adjust all the numbers
11 int minElement = *min_element(sums.begin(), sums.end());
12 minElement = -minElement;
13
14 multiset<int> elementsSet;
15 // Adjust all the numbers by the negated minimum
16 for (int num : sums) {
17 elementsSet.insert(num + minElement);
18 }
19 // Remove the zero that represents the empty subset sum
20 elementsSet.erase(elementsSet.begin());
21
22 vector<int> ans;
23 // Initialize with the smallest number
24 ans.push_back(*elementsSet.begin());
25
26 // Recover the array iteratively
27 for (int i = 1; i < n; ++i) {
28 for (int j = 0; j < (1 << i); ++j) {
29 if ((j >> (i - 1)) & 1) {
30 int sumSubset = 0;
31 // Calculate subset sum
32 for (int k = 0; k < i; ++k) {
33 if (j >> k & 1) {
34 sumSubset += ans[k];
35 }
36 }
37 // Remove the subset sum from the multiset
38 elementsSet.erase(elementsSet.find(sumSubset));
39 }
40 }
41 // The smallest element in the multiset is the next element of the array
42 ans.push_back(*elementsSet.begin());
43 }
44
45 // Find the combination that equals to the negated minimum element
46 // It will help us to know which numbers should be negative
47 for (int i = 0; i < (1 << n); ++i) {
48 int sumCombination = 0;
49 for (int j = 0; j < n; ++j) {
50 if (i >> j & 1) {
51 sumCombination += ans[j];
52 }
53 }
54 if (sumCombination == minElement) {
55 // Flip the sign of the numbers in `ans`
56 for (int j = 0; j < n; ++j) {
57 if (i >> j & 1) {
58 ans[j] = -ans[j];
59 }
60 }
61 break;
62 }
63 }
64 // Return the recovered array
65 return ans;
66 }
67};
68
1function recoverArray(n: number, sums: number[]): number[] {
2 // Find the smallest element and negate it to adjust all numbers to non-negative
3 let minElement = Math.min(...sums);
4 minElement = -minElement;
5
6 // Use a TypeScript Set for storing elements as it automatically removes duplicates
7 const elementsSet = new Set<number>();
8
9 // Adjust all numbers in the sums array
10 sums.forEach(sum => {
11 elementsSet.add(sum + minElement);
12 });
13
14 // Remove the zero that represents the empty subset sum
15 elementsSet.delete(0);
16
17 // The answer array starts with the smallest number
18 const ans: number[] = [...elementsSet][0];
19
20 // Recover the array iteratively
21 for (let i = 1; i < n; ++i) {
22 for (let j = 0; j < (1 << i); ++j) {
23 if ((j >> (i - 1)) & 1) {
24 let sumSubset = 0;
25
26 // Calculate subset sum
27 for (let k = 0; k < i; ++k) {
28 if (j >> k & 1) {
29 sumSubset += ans[k];
30 }
31 }
32
33 // Remove the subset sum from the set
34 elementsSet.delete(sumSubset);
35 }
36 }
37 // The next element of the array is the smallest element in the set
38 ans.push(Math.min(...elementsSet));
39 }
40
41 // Find the combination that equals the negated minimum element
42 for (let i = 0; i < (1 << n); ++i) {
43 let sumCombination = 0;
44
45 for (let j = 0; j < n; ++j) {
46 if (i >> j & 1) {
47 sumCombination += ans[j];
48 }
49 }
50
51 if (sumCombination === minElement) {
52 // Flip the sign of the numbers where the combination bit is set
53 for (let j = 0; j < n; ++j) {
54 if (i >> j & 1) {
55 ans[j] = -ans[j];
56 }
57 }
58 break;
59 }
60 }
61
62 // Return the recovered array
63 return ans;
64}
65
66// Example usage:
67// let inputSums: number[] = [insert your sums here];
68// let n = determine the value of n;
69// let recoveredArray = recoverArray(n, inputSums);
70
Time and Space Complexity
The given code aims to recover an array from its subset sums. It uses a sorted list to efficiently add elements and remove the smallest elements in each iteration.
Time Complexity:
The time complexity for initializing the SortedList is O(s log s)
, where s
is the number of subset sums.
The first loop has n
iterations. Inside the loop, the remove operation is called 2^i
times, where i
ranges from 0
to n-1
. The remove operation in a SortedList has a time complexity of O(log s)
due to the underlying tree structure.
Therefore, the time complexity of this outer loop is O(2^0 log s + 2^1 log s + ... + 2^(n-1) log s) = O((2^n - 1) log s)
, as the sum of powers of two up to 2^(n-1)
is 2^n - 1
.
The second loop which finds the original numbers if they're negative has up to 2^n
iterations for the subset sum calculation but is trivially only O(n)
because it is only performed once and skipped if the correct subset is not found.
Hence, the total time complexity is O(s log s + (2^n - 1) log s + n)
which simplifies to O(s log s + 2^n log s)
, under the assumption that log s
is larger than n
for practical scenarios.
Space Complexity:
The space complexity is mainly dependent on the storage for the SortedList and the answer. The SortedList sl
holds at most s
elements, hence has a space complexity of O(s)
.
The answer array ans
holds n
elements, so its space complexity is O(n)
.
The total space complexity is therefore O(s + n)
. However, since there are 2^n
subset sums and s = 2^n
, the space complexity simplifies to O(s)
.
Note: In the calculations, s
is the number of subset sums (with s = 2^n
), and n
is the length of the array to recover.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!