Problem statement

https://leetcode.com/problems/find-array-given-subset-sums/

Solution

It is quite difficult problem, and at the moment I do not have strict proof why the following solution will work.

The high level idea is the following: Imagine, we have numbers [x, y, z], then what we have is [0, x, y, z, x+y, y+z, z+x, x+y+z], but we do not know the order. If we know that one number is x, we can separate all of them into groups:

0 -> x y -> x+y z -> x+z y+z -> x+y+z.

And we can do this recursively. The problem is that we do not know x and we need to somehow guess it. I tried different strategies during contest and was not able to succeed. After contest I continued and I get the following statement:

if we sort nums, than x or -x is equal to nums[1] - nums[0]

proof Consider nums[0], that is the smallest sum we have. Let us consider original numbers t1 ... tk, 0, 0, ..., 0, s1, ... sl in non-decreasing order, where first part is negative numbers, than possibly some zeroes and finally positive. Than we can state that nums[0] = t1 + ... + tk. What about nums[1] now? It will be equal to nums[0] if we have zeroes, so it is safe to take d = 0 in this case. If we do not have zeroes, we can have two choices t1 + ... + tk + s1 or it is t1 + ... + tk - ti for some ti.

So, what to do next? We need to check these two candidates. The idea is similar to problem https://leetcode.com/problems/array-of-doubled-pairs/ : we need to sort numbers and greedily take elements: if d > 0 we start with the smallest, if d < 0, we start with the biggest. If it is possible to divide all elements into pairs with difference d (or -d), we can find this in linear time after we sort. Then we run function recursively.

Complexity

Let T(n) be time to solve problem for n. Then we have T(n) = 2*T(n-1) + O(2^n), because we split to two subproblems with size n-1 Note that we do not need to sort our data: we can do it only once in the beginning and each time sums argument we give to dfs function will be sorted. Solution of this reccurence is O(2^n * n) as well as initial sort of our data, so it will be final complexity. Space complexity is O(2^n).

Code

class Solution:
    def recoverArray(self, n, sums):
        def dfs(n, sums):
            if n == 1 and 0 in sums: return [max(sums, key = abs)]
            cands = []

            d = sums[1] - sums[0]

            for dr in [1, -1]:
                cnt, new = Counter(sums), []
                if cnt[0] == 0: return []
                for num in sums[::-dr]:
                    if cnt[num] == 0: continue
                    if cnt[num - d*dr] == 0: break
                    cnt[num] -= 1
                    new += [num]
                    cnt[num - d*dr] -= 1
                    
                if len(new) == 1 << (n-1):
                    cands += [[-d*dr] + dfs(n - 1, new[::-dr])]

            return max(cands, key = len)
        
        sums = sorted(sums)
        return dfs(n, sums)