Find Array Given Subset Sums: Divide and Reconstruct

LeetCode 1982, Find Array Given Subset Sums, gives you all 2^n subset sums of an unknown array of n integers (which may include negatives) and asks you to reconstruct any valid array.

The approach: peel off one element at a time

The key idea: sort the subset sums. The difference between the two smallest values (sums[1] - sums[0]) is a candidate for one element of the array (or its negation). You can then split the multiset of sums into two halves, one representing subsets that include this element and one representing subsets that do not. Recurse on the half without the element until you have extracted all n elements.

The tricky part is handling negative numbers. When negatives are present, sums[0] is negative (it equals the sum of all negative elements in the array). The candidate element is still sums[1] - sums[0], but you need to check whether the element itself is positive or negative by seeing which split produces a valid sub-multiset containing 0.

Here is the logic for each iteration:

1. Sort the current list of sums.
2. Compute diff = sums[1] - sums[0]. This is always non-negative.
3. Partition the sums into a "left" group (subsets without the element) and a "right" group (subsets with the element, which are each diff larger than their counterparts).
4. Check which group contains 0. If the left group has 0, the element is +diff. If the right group has 0, the element is -diff.
5. Recurse on whichever group contains 0.

After n iterations you have extracted all n elements.

The code

from collections import Counter

def recoverArray(n, sums):
    sums.sort()
    result = []

    for _ in range(n):
        diff = sums[1] - sums[0]

        left = []
        right = []
        used = Counter()

        for s in sums:
            if used[s] > 0:
                used[s] -= 1
                continue
            left.append(s)
            used[s + diff] += 1
            right.append(s + diff)

        if 0 in left:
            result.append(diff)
            sums = left
        else:
            result.append(-diff)
            sums = right

    return result

Let's walk through how the splitting works. You scan the sorted sums from left to right. For each value s, you add it to the left group (the "without" group) and mark s + diff as consumed. When you later encounter that marked value, you skip it and add it to the right group instead. This greedy pairing correctly separates the two halves because the sums are sorted.

The if 0 in left check determines the sign. The group you recurse on must represent valid subset sums of the remaining array, and every valid set of subset sums contains 0 (the empty subset). If the left group has 0, the element you extracted is positive. If only the right group has 0, the element is negative.

Visual walkthrough

Let's trace through a simple example: n = 2, sums = [0, 1, 2, 3]. The hidden array is [1, 2].

The process is clean: sort, compute the difference, split, check which side has 0, record the element, and recurse on the valid side.

Complexity

Time: You iterate n times. In each iteration, you sort the current list and scan through it. The first iteration processes 2^n elements, the second processes 2^(n-1), and so on. Sorting dominates at O(2^n * log(2^n)) = O(2^n * n) for the first pass. Summing across all iterations still gives O(2^n * n) total.

Space: You store the current list of sums, which starts at size 2^n. The Counter used for pairing also takes O(2^n) space. The result array is O(n), which is negligible compared to the sums.

The building blocks

This problem relies on two reusable techniques that appear in other problems.

Multiset splitting with a counter

The core operation is partitioning a sorted multiset into two halves where each element in the right half is exactly diff greater than its paired element in the left half. You scan left to right, greedily assigning each unconsumed value to the left and marking its partner s + diff for later consumption.

left = []
right = []
used = Counter()

for s in sorted_sums:
    if used[s] > 0:
        used[s] -= 1
        continue
    left.append(s)
    used[s + diff] += 1
    right.append(s + diff)

This pairing technique shows up whenever you need to match elements across two groups based on a fixed offset, for example in problems involving difference pairs or complementary subsets.

Recursive peeling

The strategy of extracting one element per iteration and reducing the problem size by half is a form of divide-and-conquer. You go from 2^n sums to 2^(n-1) sums each round, peeling off one array element at a time. This "reduce by one dimension" approach appears in problems like constructing a binary tree from traversals, where each recursive call identifies one node and splits the remaining data.

Edge cases

All positive elements: When every element is positive, sums[0] is always 0 (the empty subset). The left group always contains 0, so every extracted element is positive. This is the simplest case.

Negative elements present: If the array has negatives, sums[0] is the sum of all negative elements. The candidate diff is still sums[1] - sums[0], but you might need to take -diff as the actual element. The 0-in-left-or-right check handles this automatically.

Zeros in the array: If the array contains 0, then diff = sums[1] - sums[0] = 0 on some iteration. The two groups become identical (adding 0 does not change a sum). Both groups contain 0, so you pick +0 and recurse on either group. The algorithm handles this correctly.

Single element (n = 1): The sums list has exactly two values: [0, x] (if x is non-negative) or [x, 0] (if x is negative). One iteration extracts diff = sums[1] - sums[0], checks the sign, and returns.

From understanding to recall

The algorithm has a simple loop structure: sort, compute diff, split, check sign, recurse. But the splitting logic is where mistakes happen under pressure. The key detail to remember is the scanning order: you process the sums from smallest to largest, always assigning the current value to the left group and marking s + diff as used. If you try to go right-to-left or pair differently, the greedy matching breaks.

Practice writing the inner loop from scratch. The Counter tracks how many copies of each value are "spoken for" by a left-group partner. When you encounter a value that is already spoken for, it belongs to the right group. This invariant is what you need to internalize.

A few spaced repetition sessions focused on the splitting loop will make the implementation feel natural. You will stop worrying about off-by-one issues with the counter because the invariant guides every decision.

Related posts

• First Missing Positive - Another hard array problem where the key insight is using the data structure itself (the array or the multiset) to encode information, rather than allocating extra storage
• Maximum Subarray - A classic divide-and-conquer array problem where you split the array in half and combine results, illustrating the same recursive reduction pattern
• Reverse Pairs - Uses a merge-sort-based divide-and-conquer on arrays, splitting and recombining in a way that mirrors the subset sum partitioning idea