1982. Find Array Given Subset Sums

HardArrayDivide and Conquer
Leetcode Link

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:

  1. The smallest value in the sums array must be the sum of an empty subset, thus it should be 0. If not, that implies that all subsets include a negative number, which is also the minimum value of the original array.

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

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

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

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

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:

  1. 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 in sums to "re-adjust" the subset sums as if they were calculated with the original array having no negatives. A SortedList is used for sums with the re-adjusted values.

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

  3. 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 from sums list. This works because, with each new element of ans, you form new subsets that combine the new element with all previous subsets.

  4. 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 sum s for a given subset indicated by j (binary representation of j indicates which elements to include), and then s is removed from the sorted list.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

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?

Example 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:

  1. Initialize Adjustments: We begin by identifying the minimum element in the subset sums, which should be 0. In this example, the smallest value is indeed 0, so there's no need to adjust the sums array for negative numbers.

  2. Start Building the Array: We remove the first element which is 0 from the sorted sums, since this corresponds to the empty subset. The next smallest value is 1, which we take as the first element of the original array (ans[0] = 1).

  3. 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 be 1 (from ans[0] itself) and 2 (which includes ans[0] and the unknown second element).
    • We remove 1 and 2 from the sums array, and we are left with [1].

  4. 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 in sums is 1, we deduce that ans[1] = 1.

  5. 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
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Divide and Conquer Intro

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫