Find Array Given Subset Sums

Find Array Given Subset Sums

What is this problem about?

The Find Array Given Subset Sums coding problem is a challenging mathematical puzzle. You are given an array sums containing all $2^n$ possible subset sums of an unknown array of length $n$. Your task is to reconstruct the original array. The original array can contain negative integers.

Why is this asked in interviews?

This "Hard" difficulty problem is used by companies like Mindtickle to test a candidate's mastery of Divide and Conquer and combinatorial logic. Reconstructing a set from its subset sums requires a deep understanding of how the presence of a single element $x$ splits the set of sums into two halves: those that include $x$ and those that don't. It evaluation your ability to handle complex recursion and identify mathematical invariants.

Algorithmic pattern used

This problem uses a recursive Divide and Conquer strategy.

1. Sort the sums array.
2. The smallest element difference (often sums[1] - sums[0]) is a candidate for an element $x$ in the original array.
3. Split the sums into two equal-sized arrays: S0 (sums not containing $x$) and S1 (sums containing $x$).
   • This is done by iterating through the sorted sums and pairing up $s$ and $s+x$.
4. Check which of the two arrays (S0 or S1) contains the sum 0. If S0 has 0, then $x$ is part of the original array. If S1 has 0, then $-x$ is part of the original array (and we continue with S1).
5. Recursively repeat the process with the chosen half until you have found $n$ elements.

Example explanation

$n = 2$, sums = [0, 1, 2, 3]

1. Sorted sums: [0, 1, 2, 3].
2. Difference $x = sums[1] - sums[0] = 1 - 0 = 1$.
3. Try splitting with $x = 1$:
   • $0$ pairs with $1$.
   • $2$ pairs with $3$.
   • S0 = [0, 2], S1 = [1, 3].
4. Since S0 contains 0, $x = 1$ is an element.
5. Repeat for sums = [0, 2]. Difference $x = 2 - 0 = 2$.
6. Final array: [1, 2].

Common mistakes candidates make

• Not sorting: The pairings only work reliably if the sums are sorted.
• Handling negative numbers: Failing to realize that if 0 ends up in the "shifted" array S1, it means the original element was negative.
• Complexity: Attempting to use a brute-force combination check, which is $O(2^N imes 2^N)$—impossible for $n=15$.

Interview preparation tip

This problem is essentially the inverse of the subset sum problem. When dealing with power sets or subset sums, look for the smallest or largest gaps. These gaps often reveal the individual elements that were used to build the sum.