Find Array Given Subset Sums LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> recoverArray(int n, vector<int> &sums) {
4
    sort(sums.begin(), sums.end());
5

6
    vector<int> ans;
7
    while (n--) {
8
      int diff = sums[1] - sums[0];
9
      unordered_map<int, int> freq;
10
      vector<int> ss0, ss1;
11
      bool on = false;
12
      for (auto &x : sums)
13
        if (!freq[x]) {
14
          ss0.push_back(x);
15
          freq[x + diff]++;
16
          if (x == 0) on = true;
17
        } else {
18
          ss1.push_back(x);
19
          freq[x]--;
20
        }
21
      if (on) {
22
        ans.push_back(diff);
23
        sums = ss0;
24
      } else {
25
        ans.push_back(-diff);
26
        sums = ss1;
27
      }
28
    }
29
    return ans;
30
  }
31
};