(复杂dfs, 周赛t4)1982. 从子集的和还原数组

1982. 从子集的和还原数组

题解

class Solution {
 public:
  vector<int> dfs(int n, vector<int>& arr) {
    if (n == 1) {
      if (arr[0] == 0) return {arr[1]};
      if (arr[1] == 0) return {arr[0]};
      return {};
    }
    int d = arr[1] - arr[0];
    vector<int> s, t;
    vector<bool> used(arr.size());
    int left = 0, right = 0;
    while (true) {
      while (left < arr.size() && used[left]) left++;
      if (left == arr.size()) break;
      used[left] = true;
      s.push_back(arr[left]);

      while (used[right] || arr[left] + d != arr[right]) right++;

      t.push_back(arr[right]);
      used[right] = true;
    }

    vector<int> res;
    res = dfs(n - 1, s);
    if (!res.empty()) {
      res.push_back(d);
      return res;
    }
    res = dfs(n - 1, t);
    if (!res.empty()) {
      res.push_back(-d);
      return res;
    }
    return {};
  }
  vector<int> recoverArray(int n, vector<int>& sums) {
    sort(sums.begin(), sums.end());
    return dfs(n, sums);
  }
};