Welcome to Subscribe On Youtube
1982. Find Array Given Subset Sums
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 2n 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 - [1]: sum is 1 - [2]: sum is 2 - [1,2]: sum is 3 - [-3]: sum is -3 - [1,-3]: sum is -2 - [2,-3]: sum is -1 - [1,2,-3]: 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 <= 15sums.length == 2n-104 <= sums[i] <= 104
Solutions
Solution 1: Bit Manipulation
This implementation uses bit manipulation. It traverses the relevant values and updates its state as each value is processed. Ordering the data first makes the subsequent comparisons deterministic. After all required states have been considered, the maintained result is returned.
Solution 2
This implementation uses sorting, followed by hash table, followed by bit manipulation. It traverses the relevant values and updates its state as each value is processed. A keyed container records values that must be found or updated efficiently. Ordering the data first makes the subsequent comparisons deterministic.
-
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; } } // Solution 2 class Solution { public int[] recoverArray(int n, int[] sums) { Arrays.sort(sums); int[] sums1 = new int[1 << n]; int[] sums2 = new int[1 << n]; Map<Integer, Integer> cnt = new HashMap<>(); int[] ans = new int[n]; for (int i = n; i > 0; --i) { int k = 1 << i; int d = sums[k - 1] - sums[k - 2]; cnt.clear(); for (int j = 0; j < k; ++j) { cnt.merge(sums[j], 1, Integer::sum); } int sign = 1; for (int j = 0, p = 0; j < k; ++j) { if (cnt.getOrDefault(sums[j], 0) == 0) { continue; } cnt.merge(sums[j], -1, Integer::sum); cnt.merge(sums[j] + d, -1, Integer::sum); sums1[p] = sums[j]; sums2[p++] = sums[j] + d; if (sums[j] + d == 0) { sign = -1; } } ans[i - 1] = sign * d; System.arraycopy(sign == 1 ? sums1 : sums2, 0, sums, 0, k / 2); } return ans; } } -
class Solution { public: vector<int> recoverArray(int n, vector<int>& sums) { int m = *min_element(sums.begin(), sums.end()); m = -m; multiset<int> st; for (int x : sums) { st.insert(x + m); } st.erase(st.begin()); vector<int> ans; ans.push_back(*st.begin()); for (int i = 1; i < n; ++i) { for (int j = 0; j < 1 << i; ++j) { if (j >> (i - 1) & 1) { int s = 0; for (int k = 0; k < i; ++k) { if (j >> k & 1) { s += ans[k]; } } st.erase(st.find(s)); } } ans.push_back(*st.begin()); } for (int i = 0; i < 1 << n; ++i) { int s = 0; for (int j = 0; j < n; ++j) { if (i >> j & 1) { s += ans[j]; } } if (s == m) { for (int j = 0; j < n; ++j) { if (i >> j & 1) { ans[j] = -ans[j]; } } break; } } return ans; } }; // Solution 2 class Solution { public: vector<int> recoverArray(int n, vector<int>& sums) { sort(sums.begin(), sums.end()); vector<int> ans(n); unordered_map<int, int> cnt; for (int i = n; i; --i) { cnt.clear(); int k = 1 << i; int d = sums[k - 1] - sums[k - 2]; for (int j = 0; j < k; ++j) { cnt[sums[j]]++; } vector<int> sums1, sums2; int sign = 1; for (int j = 0; j < k; ++j) { if (cnt[sums[j]] == 0) { continue; } --cnt[sums[j]]; --cnt[sums[j] + d]; sums1.push_back(sums[j]); sums2.push_back(sums[j] + d); if (sums2.back() == 0) { sign = -1; } } ans[i - 1] = sign * d; for (int j = 0; j < k / 2; ++j) { sums[j] = sign == 1 ? sums1[j] : sums2[j]; } } 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 # Solution 2 class Solution: def recoverArray(self, n: int, sums: List[int]) -> List[int]: sums.sort() ans = [] for i in range(n, 0, -1): k = 1 << i d = sums[k - 1] - sums[k - 2] cnt = Counter(sums[:k]) sums1, sums2 = [], [] sign = 1 for s in sums[:k]: if not cnt[s]: continue cnt[s] -= 1 cnt[s + d] -= 1 sums1.append(s) sums2.append(s + d) if s + d == 0: sign = -1 ans.append(sign * d) sums = sums1 if sign == 1 else sums2 return ans -
func recoverArray(n int, sums []int) []int { m := -slices.Min(sums) 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 } // Solution 2 func recoverArray(n int, sums []int) (ans []int) { sort.Ints(sums) for i := n; i > 0; i-- { k := 1 << i d := sums[k-1] - sums[k-2] cnt := map[int]int{} for _, s := range sums[:k] { cnt[s]++ } sums1, sums2 := []int{}, []int{} sign := 1 for _, s := range sums[:k] { if cnt[s] == 0 { continue } cnt[s]-- cnt[s+d]-- sums1 = append(sums1, s) sums2 = append(sums2, s+d) if s+d == 0 { sign = -1 } } ans = append(ans, sign*d) if sign == -1 { sums1 = sums2 } sums = sums1 } return } -
class Solution { public int[] recoverArray(int n, int[] sums) { Arrays.sort(sums); int[] sums1 = new int[1 << n]; int[] sums2 = new int[1 << n]; Map<Integer, Integer> cnt = new HashMap<>(); int[] ans = new int[n]; for (int i = n; i > 0; --i) { int k = 1 << i; int d = sums[k - 1] - sums[k - 2]; cnt.clear(); for (int j = 0; j < k; ++j) { cnt.merge(sums[j], 1, Integer::sum); } int sign = 1; for (int j = 0, p = 0; j < k; ++j) { if (cnt.getOrDefault(sums[j], 0) == 0) { continue; } cnt.merge(sums[j], -1, Integer::sum); cnt.merge(sums[j] + d, -1, Integer::sum); sums1[p] = sums[j]; sums2[p++] = sums[j] + d; if (sums[j] + d == 0) { sign = -1; } } ans[i - 1] = sign * d; System.arraycopy(sign == 1 ? sums1 : sums2, 0, sums, 0, k / 2); } return ans; } } -
class Solution { public: vector<int> recoverArray(int n, vector<int>& sums) { sort(sums.begin(), sums.end()); vector<int> ans(n); unordered_map<int, int> cnt; for (int i = n; i; --i) { cnt.clear(); int k = 1 << i; int d = sums[k - 1] - sums[k - 2]; for (int j = 0; j < k; ++j) { cnt[sums[j]]++; } vector<int> sums1, sums2; int sign = 1; for (int j = 0; j < k; ++j) { if (cnt[sums[j]] == 0) { continue; } --cnt[sums[j]]; --cnt[sums[j] + d]; sums1.push_back(sums[j]); sums2.push_back(sums[j] + d); if (sums2.back() == 0) { sign = -1; } } ans[i - 1] = sign * d; for (int j = 0; j < k / 2; ++j) { sums[j] = sign == 1 ? sums1[j] : sums2[j]; } } return ans; } }; -
class Solution: def recoverArray(self, n: int, sums: List[int]) -> List[int]: sums.sort() ans = [] for i in range(n, 0, -1): k = 1 << i d = sums[k - 1] - sums[k - 2] cnt = Counter(sums[:k]) sums1, sums2 = [], [] sign = 1 for s in sums[:k]: if not cnt[s]: continue cnt[s] -= 1 cnt[s + d] -= 1 sums1.append(s) sums2.append(s + d) if s + d == 0: sign = -1 ans.append(sign * d) sums = sums1 if sign == 1 else sums2 return ans -
func recoverArray(n int, sums []int) (ans []int) { sort.Ints(sums) for i := n; i > 0; i-- { k := 1 << i d := sums[k-1] - sums[k-2] cnt := map[int]int{} for _, s := range sums[:k] { cnt[s]++ } sums1, sums2 := []int{}, []int{} sign := 1 for _, s := range sums[:k] { if cnt[s] == 0 { continue } cnt[s]-- cnt[s+d]-- sums1 = append(sums1, s) sums2 = append(sums2, s+d) if s+d == 0 { sign = -1 } } ans = append(ans, sign*d) if sign == -1 { sums1 = sums2 } sums = sums1 } return }