Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1982.html

1982. Find Array Given Subset Sums

Level

Hard

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.

An array sub is a subset of an array arr if sub can be obtained from arr by deleting some (possibly zero or all) elements of arr. The sum of the elements in sub is one possible subset sum of arr. The sum of an empty array is considered to be 0.

Note: Test cases are generated such that there will always be at least one correct answer.

Example 1:

Input: n = 3, sums = [-3,-2,-1,0,0,1,2,3]

Output: 1,2,-3

Explanation: 1,2,-3 is able to achieve the given subset sums:

  • []: sum is 0

Note that any permutation of 1,2,-3 and also any permutation of [-1,-2,3] will also be accepted.

Example 2:

Input: n = 2, sums = [0,0,0,0]

Output: [0,0]

Explanation: The only correct answer is [0,0].

Example 3:

Input: n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]

Output: [0,-1,4,5]

Explanation: [0,-1,4,5] is able to achieve the given subset sums.

Constraints:

  • 1 <= n <= 15
  • sums.length == 2^n
  • -10^4 <= sums[i] <= 10^4

Solution

The minimum element in sums is the sum of all negative elements in the original array, and the difference between the second minimum element in sums and the minimum element in sums is the minimum absolute value among all elements in the original array. Use minNum to represent the element with the minimum absolute value. Divide sums into two parts such that one part is the result of adding minNum to each element in the other part. Repeat n times to recover the original array.

  • class Solution {
    public int[] recoverArray(int n, int[] sums) {
        int total = 0;
        for (int num : sums)
            total += num;
        int sum = total / (1 << n - 1);
        Arrays.sort(sums);
        int[] arr = new int[n];
        List<Integer> sumsList = new ArrayList<Integer>();
        for (int num : sums)
            sumsList.add(num);
        List<Integer> small = new ArrayList<Integer>();
        List<Integer> large = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            int size = sumsList.size();
            boolean[] selected = new boolean[size];
            int minNum = sumsList.get(1) - sumsList.get(0);
            boolean flag = false;
            for (int j = 0; j < size; j++) {
                if (!selected[j]) {
                    selected[j] = true;
                    small.add(sumsList.get(j));
                    for (int k = j + 1; k < size; k++) {
                        if (!selected[k] && sumsList.get(k) == sumsList.get(j) + minNum) {
                            selected[k] = true;
                            large.add(sumsList.get(k));
                            if (minNum == sumsList.get(k))
                                flag = true;
                            break;
                        }
                    }
                }
            }
            sumsList.clear();
            if (flag)
                sumsList = new ArrayList<Integer>(small);
            else {
                sumsList = new ArrayList<Integer>(large);
                minNum = -minNum;
            }
            small.clear();
            large.clear();
            arr[i] = minNum;
        }
        return arr;
    }
}

############

class Solution {
    public int[] recoverArray(int n, int[] sums) {
        int m = 1 << 30;
        for (int x : sums) {
            m = Math.min(m, x);
        }
        m = -m;
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int x : sums) {
            tm.merge(x + m, 1, Integer::sum);
        }
        int[] ans = new int[n];
        if (tm.merge(0, -1, Integer::sum) == 0) {
            tm.remove(0);
        }
        ans[0] = tm.firstKey();
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < 1 << i; ++j) {
                if ((j >> (i - 1) & 1) == 1) {
                    int s = 0;
                    for (int k = 0; k < i; ++k) {
                        if (((j >> k) & 1) == 1) {
                            s += ans[k];
                        }
                    }
                    if (tm.merge(s, -1, Integer::sum) == 0) {
                        tm.remove(s);
                    }
                }
            }
            ans[i] = tm.firstKey();
        }
        for (int i = 0; i < 1 << n; ++i) {
            int s = 0;
            for (int j = 0; j < n; ++j) {
                if (((i >> j) & 1) == 1) {
                    s += ans[j];
                }
            }
            if (s == m) {
                for (int j = 0; j < n; ++j) {
                    if (((i >> j) & 1) == 1) {
                        ans[j] *= -1;
                    }
                }
                break;
            }
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/find-array-given-subset-sums/
// Time: O(2^N * N)
// Space: O(2^N)
class Solution {
public:
    vector<int> recoverArray(int n, vector<int>& A) {
        sort(begin(A), end(A));
        int mn = A[0];
        for (int &n : A) n -= mn;
        vector<int> ans, next;
        while (n--) {
            int num = A[1], j = 0;
            next.clear();
            for (int i = 0; i < A.size(); ++i) {
                if (j < next.size() && A[i] == next[j] + num) ++j;
                else next.push_back(A[i]);
            }
            ans.push_back(num);
            swap(next, A);
        }
        function<bool(int, int)> dfs = [&](int sum, int i) {
            if (sum == 0) return true;
            if (i == ans.size()) return false;
            int num = ans[i];
            ans[i] = -num;
            if (dfs(sum - num, i + 1)) return true;
            ans[i] = num;
            return dfs(sum, i + 1);
        };
        dfs(-mn, 0);
        return ans;
    }
};

  • from sortedcontainers import SortedList


class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        m = -min(sums)
        sl = SortedList(x + m for x in sums)
        sl.remove(0)
        ans = [sl[0]]
        for i in range(1, n):
            for j in range(1 << i):
                if j >> (i - 1) & 1:
                    s = sum(ans[k] for k in range(i) if j >> k & 1)
                    sl.remove(s)
            ans.append(sl[0])
        for i in range(1 << n):
            s = sum(ans[j] for j in range(n) if i >> j & 1)
            if s == m:
                for j in range(n):
                    if i >> j & 1:
                        ans[j] *= -1
                break
        return ans


  • func recoverArray(n int, sums []int) []int {
	m := 0
	for _, x := range sums {
		m = min(m, x)
	}
	m = -m
	rbt := redblacktree.NewWithIntComparator()
	merge := func(key int, value int) {
		if v, ok := rbt.Get(key); ok {
			nxt := v.(int) + value
			if nxt == 0 {
				rbt.Remove(key)
			} else {
				rbt.Put(key, nxt)
			}
		} else {
			rbt.Put(key, value)
		}
	}
	for _, x := range sums {
		merge(x+m, 1)
	}
	ans := make([]int, n)
	merge(ans[0], -1)
	ans[0] = rbt.Left().Key.(int)
	for i := 1; i < n; i++ {
		for j := 0; j < 1<<i; j++ {
			if j>>(i-1)&1 == 1 {
				s := 0
				for k := 0; k < i; k++ {
					if j>>k&1 == 1 {
						s += ans[k]
					}
				}
				merge(s, -1)
			}
		}
		ans[i] = rbt.Left().Key.(int)
	}
	for i := 0; i < 1<<n; i++ {
		s := 0
		for j := 0; j < n; j++ {
			if i>>j&1 == 1 {
				s += ans[j]
			}
		}
		if s == m {
			for j := 0; j < n; j++ {
				if i>>j&1 == 1 {
					ans[j] = -ans[j]
				}
			}
			break
		}
	}
	return ans

}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

All Problems

All Solutions