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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Array Given Subset Sums

Number: 2109

Difficulty: Hard

Paid? No

Companies: Mindtickle

Problem Description

Given an integer n representing the length of an unknown array and an array sums containing the 2^n subset sums (in no particular order) of the unknown array, recover any valid original array which could have produced these subset sums. The empty subset is included (with sum 0). If multiple answers exist, any one is acceptable.

Key Insights

  • The sorted list of subset sums always starts with 0.
  • The second smallest element in the sorted subset sums is the smallest element in the unknown array.
  • Once an element is identified, the subset sums that include this element can be “removed” from the multiset of sums.
  • A multiset (or counter) is used to keep track of frequencies of current sums so that duplicates are properly handled.
  • Repeating this process iteratively recovers all n elements of the unknown array.

Space and Time Complexity

Time Complexity: O(n * 2^n) in the worst case, since for each of the n recovered elements we process a subset of size roughly 2^n. Space Complexity: O(2^n) for storing the multiset (or counter) of subset sums.

Solution

The main idea is to iteratively determine one element of the original array at a time. Start by sorting the subset sums. The smallest element (0) represents the empty subset, and the next smallest value is the smallest element in the original array. Once this candidate element is identified, generate all new subset sums by adding this element to every previously found subset sum (starting with just 0). Remove these newly generated sums from the existing multiset of subset sums. This “removal” effectively partitions the sums into those that include the candidate and those that do not. Then, repeat the process for the remaining elements until all n elements have been recovered. Data structures used include a multiset (or counter/dictionary) to track frequency and a list to hold the current subset sums built from found elements.

Code Solutions

# Python solution using a Counter for the multiset
from collections import Counter
from typing import List

class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        # Sort the sums and initialize a Counter for frequency
        multiset = Counter(sorted(sums))
        ans = []          # Stores the recovered array
        current_subs = [0]  # Initially, the only subset sum is 0 from the empty subset

        for _ in range(n):
            # The smallest non-zero element in the sorted keys (since 0 is always present)
            for key in sorted(multiset):
                if key != 0:
                    candidate = key
                    break
            ans.append(candidate)
            
            # Generate new subset sums by adding candidate to every sum in current_subs
            new_subs = []
            for value in current_subs:
                new_subs.append(value + candidate)
            # Sort new_subs to ensure a consistent removal order from the multiset
            new_subs.sort()
            
            # Remove each sum in new_subs from the multiset once
            for num in new_subs:
                multiset[num] -= 1
                if multiset[num] == 0:
                    del multiset[num]
            # Merge the new subset sums to current_subs for next iteration
            current_subs += new_subs

        return ans

# Example usage:
# sol = Solution()
# print(sol.recoverArray(3, [-3,-2,-1,0,0,1,2,3]))  # Output may be [1,2,-3] or another valid array
← Back to All Questions