Question

1982. 从子集的和还原数组

English Version

题目描述

存在一个未知数组需要你进行还原，给你一个整数 n 表示该数组的长度。另给你一个数组 sums ，由未知数组中全部 2n 个 子集的和 组成（子集中的元素没有特定的顺序）。

返回一个长度为 n 的数组_ _ans_ _表示还原得到的未知数组。如果存在 多种 答案，只需返回其中 任意一个 。

如果可以由数组 arr 删除部分元素（也可能不删除或全删除）得到数组 sub ，那么数组 sub 就是数组 arr 的一个 子集 。sub 的元素之和就是 arr 的一个 子集的和 。一个空数组的元素之和为 0 。

注意：生成的测试用例将保证至少存在一个正确答案。

 

示例 1：

输入：n = 3, sums = [-3,-2,-1,0,0,1,2,3]
输出：[1,2,-3]
解释：[1,2,-3] 能够满足给出的子集的和：
- []：和是 0
- [1]：和是 1
- [2]：和是 2
- [1,2]：和是 3
- [-3]：和是 -3
- [1,-3]：和是 -2
- [2,-3]：和是 -1
- [1,2,-3]：和是 0
注意，[1,2,-3] 的任何排列和 [-1,-2,3] 的任何排列都会被视作正确答案。

示例 2：

输入：n = 2, sums = [0,0,0,0]
输出：[0,0]
解释：唯一的正确答案是 [0,0] 。

示例 3：

输入：n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]
输出：[0,-1,4,5]
解释：[0,-1,4,5] 能够满足给出的子集的和。

 

提示：

• 1 <= n <= 15
• sums.length == 2n
• -104 <= sums[i] <= 104

解法

方法一

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

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;
  }
}

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;
  }
};

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

}

方法二

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

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;
  }
};

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
}