{x}
blog image

Find Array Given Subset Sums

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

Problem Description

The problem asks to recover an unknown array of length n given an array sums containing all 2n subset sums of the unknown array. The solution should return the unknown array. Multiple solutions may exist, and any one is acceptable.

Solution Explanation

The solutions leverage the properties of subset sums. The core idea revolves around iteratively finding the elements of the unknown array.

Solution 1 (Iterative Approach):

This solution uses a clever iterative approach. It first finds the minimum element in the sums array, negates it, and adds it to all elements in sums. This transformation makes sure that there is always a zero. This operation ensures that 0 is included in sums. Then it iteratively identifies the elements of the unknown array.

  1. Initialization:

    • Find the minimum value (m) in sums. The negative of this minimum value will be added to all values in sums.
    • Sort the sums array to streamline the element extraction process. Remove 0 from the array if present.

  2. Iterative Element Extraction:

    • The first element of the sorted sums (after the transformation) is the first element of the unknown array.
    • In each iteration, the algorithm considers all possible subset sums that can be formed using the previously discovered array elements. These subset sums are removed from sums, leaving the next element of the unknown array as the smallest remaining value. This process continues until all n elements are found.

  3. Sign Correction:

    • After finding all n elements, a final check is performed to adjust the signs of the elements if the condition is not satisfied. This ensures that the set of subset sums can be generated from the output array.

Solution 2 (Recursive Approach):

This approach sorts the sums array and uses a recursive strategy. It finds the difference between consecutive sums and uses this difference as a potential element of the unknown array.

  1. Sorting: Sort the sums array to make it easier to find the difference between consecutive sums.

  2. Recursive Step:

    • At each step, it calculates the difference between consecutive elements (e.g., sums[1] - sums[0]) representing the potential element.
    • If the element is found, then it divides the subsets into two sets: one without the found element, and another including the found element. It removes the sums that can be created by adding the element to the sums of the first set.
    • This process repeats recursively for the remaining sums until all elements are found.
    • The sign of the element is adjusted if it's required.

Time Complexity Analysis:

  • Solution 1: The time complexity is dominated by the nested loops in the element extraction step. The outer loop iterates n times, and the inner loop iterates 2i times in the i-th iteration. So, the overall time complexity is O(n * 2n).

  • Solution 2: The time complexity is dominated by the sorting step, which takes O(2n log 2n) = O(n * 2n) time and the recursive calls, which also amounts to approximately O(n * 2n) operations in the worst case.

Space Complexity Analysis:

  • Solution 1: The space complexity is O(2n) due to the sums array and the auxiliary space used.

  • Solution 2: The space complexity is O(2n) to store the sorted sums array and for recursion overhead.

Both solutions offer correct results, but Solution 1 might be slightly more efficient in practice due to a potentially better constant factor in its time complexity. The choice depends on the preference for iterative vs recursive approaches.