(C++) 2122. Recover the Original Array
\n\nclass Solution {\npublic:\n    vector<int> recoverArray(vector<int>& nums) {\n        sort(nums.begin(), nums.end()); \n        \n        map<int, int> cnt;
\n```\nclass Solution {\npublic:\n    vector<int> recoverArray(vector<int>& nums) {\n        sort(nums.begin(), nums.end()); \n        \n        map<int, int> cnt; \n        for (auto& x : nums) ++cnt[x]; \n        \n        vector<int> ans; \n        for (int i = 1; i < nums.size(); ++i) {\n            int diff = nums[i] - nums[0]; \n            if (diff && diff % 2 == 0) {\n                ans.clear(); \n                bool found = true; \n                map<int, int> freq = cnt; \n                for (auto& [k, v] : freq) {\n                    if (v) {\n                        if (freq[k + diff] < v) {found = false; break;}\n                        freq[k+diff] -= v; \n                        for (; v; --v) ans.push_back(k+diff/2); \n                    }\n                }\n                if (found) break; \n            }\n        }\n        return ans; \n    }\n};\n```
['C']