We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Array Given Subset Sums

Difficulty: Hard

Problem Description

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

Key Insights

  • Each subset of the unknown array contributes to the total subset sums.
  • The number of subset sums is 2^n, where n is the length of the unknown array.
  • The sum of elements in the unknown array must be considered to derive the subset sums.
  • The smallest element in the subset sums must be part of the unknown array.

Space and Time Complexity

Time Complexity: O(n * 2^n)
Space Complexity: O(2^n)

Solution

The solution involves using a multiset to track the subset sums and iteratively reconstructing the unknown array. The approach is as follows:

  1. Sort the input sums to easily access the smallest elements.
  2. Use a multiset (or a hashmap) to handle the occurrences of subset sums.
  3. Begin with the smallest subset sum (which is always zero) and iteratively add the next smallest element to the unknown array while updating the multiset to reflect the new subset sums generated by this addition.
  4. Continue this process until the unknown array of length n is reconstructed.

Code Solutions

from collections import Counter

def findArray(n, sums):
    sums.sort()
    result = []
    subset_counter = Counter(sums)
    
    # The first element is always 0 (the empty subset)
    subset_counter[0] -= 1
    
    # Start building the result array
    for _ in range(n):
        # The next number to add to the result array
        x = next((key for key in subset_counter if subset_counter[key] > 0), None)
        result.append(x)
        
        # Generate new subset sums with the new element x
        new_sums = []
        for y in result:
            new_sums.append(x + y)
        
        # Update the multiset with the new sums
        for new_sum in new_sums:
            subset_counter[new_sum] -= 1
            
    return result
← Back to All Questions